AtCoder Regular Contest #004 C: 平均値太郎の憂鬱

問題

ここ参照。

方針

本番中は二分探索をしていた。ほとんどのケースは通っていたのだけれど、いくつかのケースで落ちていた。分数が既約分数だと思い込んでいたけど、そうじゃない場合もあるようだ。おそらく落ちた原因はそれだと思う。
二分探索よりスマートでシンプルな解法があって、以下の2次不等式をiについて解けばよい。

平方根とか出てくるけど、マージンを取るような方向の近い整数に丸めるとよい。

ソースコード

using namespace std;

#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)

long long gcd(long long a, long long b) {
    if (!b)
        return a;
    return gcd(b, a%b);
}


int main() {
    long long x, y;
    char c;

    cin >> x >> c >> y;
    long long g = gcd(x, y);
    x /= g;
    y /= g;
    
    bool res = false;
    for (long long i = (2*x-y)/y/y; i <= (2*x+y)/y/y+1; i++) {
        long long n = i*y;
        long long sum = n*(n+1)/2;
        long long m = sum - i*x;
        if (1 <= m && m <= n) {
            res = true;
            cout << n << " " << m << endl;
        }
    }

    if (!res)
        puts("Impossible");
    return 0;
}