Codeforces #172 Div2 B "Nearest Fraction"

問題

整数 X Y Nが与えられる。
X / Yに最も近い値をA / Bの形で出力しなさい。
ただし、B <= Nに制限される。
候補が２つ以上ある場合、なるべくBの小さいものを、
それでもまだ複数ある場合Aの小さいものを出力しなさい。

制約

1 <= X, Y, N <= 10^5

考えた事

10^5か・・
1 <= B <= N, 1 <= A <= X / Yで全探索したら
計算量でだめだな。

A / B <= X / Yとなるような、最も大きいAから始めよう

ん？そのようなAであれば、
A / B <= X / Y <= (A+1) / Bになるから、
それぞれのBで探索すべきAは２個だけだな、よしいける！

WA

doubleの誤差かな？
じゃあ暫定結果の分数と確かめる分数とX / Yの分数の
分母を合わせちゃって、整数で比較できるようにしよう！

WA

あ、10^5*10^5*10^5でintがオーバーフローしてたは

AC

ソースコード

typedef long long ll;

int main() {
    ll X, Y, N;
    cin >> X >> Y >> N;

    ll A = 1, B = 1; // 暫定チャンピオン
    for( ll b = N; b >= 1; b-- ){
        ll a = b * X / Y + 1; // X / Y <= (A+1) / B
        ll to = B * b * X;  // 近づくべき値
        ll att = B * Y * a; // 挑戦者の値
        ll def = b * Y * A; // チャンピオンの値

        if( abs( to - def ) >= abs( to - att ) ){
            A = a; B = b;
        }

        a = a - 1; // A / B <= X / Y
        att = B * Y * a;

        if( abs( to - def ) >= abs( to - att ) ){
            A = a; B = b;
        }
    }
    cout << A << '/' << B << endl;
}