問題
が与えられるのでを満たし$$ \frac{\frac{N (N + 1)}{2} - M}{N} = \frac{X}{Y}$$であるを全て求めて列挙せよ。
解法
式変形をすると$$N = 2\frac{X}{Y} + 2\frac{M}{N} - 1$$でありであるので、としてあり得るのはまたはの2通り。それらについてを計算して条件を満たすかチェックすればよい。
反省
30WAくらい出してしまった。原因は範囲の絞り方がおかしかったりPythonでよくわからないWAを出しまくったり、順番を逆にしていたりなど。
式変形で上のような絞り方をするのが思いついてこなかった。数字が大きいのでオーバーフローに気を付けて式変形しなければならない。大小関係から]の範囲に落とし込むテクは重要そう。特に整数の問題ならそれでかなり絞れる。
とにかく苦労が多い問題だった。
コード
#include"bits/stdc++.h" using namespace std; using ll = int64_t; ll gcd(ll a, ll b) { return (b ? gcd(b, a % b) : a); } int main() { string s; cin >> s; ll X = 0, Y = 0; bool slash = false; for (char c : s) { if (c == '/') { slash = true; } else if (!slash) { X *= 10; X += c - '0'; } else { Y *= 10; Y += c - '0'; } } ll k = gcd(X, Y); X /= k; Y /= k; vector<pair<ll, ll>> ans; for (ll i = 0; i < 2; i++) { ll N = 2 * X / Y + i; if (N % Y == 0) { ll M = N * (N + 1) / 2 - N / Y * X; if (1 <= M && M <= N) { ans.push_back({ N, M }); } } } if (ans.size()) { for (auto p : ans) { cout << p.first << " " << p.second << endl; } } else { cout << "Impossible" << endl; } }