AtCoder Regular Contest 004 C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )

問題

　が与えられるのでを満たし$$ \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;
    }
}