けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Chokudai SpeedRun 002 H - あまり β (400 点)

発想一発ゲー!!!楽しい

問題へのリンク

問題概要

 N 個の以下の問題に答えてください。

  • 整数  A_i を割った余りと整数  B_i を割った余りが等しくなるような正整数のうち最大のものを求めよ

制約

  •  1 \le N \le 2 × 10^{5}

考えたこと

 A_i = B_i だったら、任意の整数が条件を満たすので、-1。それはそう

それ以外のときは、ようするにあまり  r を決めると  A_{i} - r B_{i} - r の公約数のうち  r より大きいものが答え  X の候補になるのだけど、

  •  A_{i} = Xp + r
  •  B_{i} = Xq + r

と書いてみると、一般性を失わずに  A_{i} \gt B_{i} として

  •  A_{i} - B_{i} = X(p - q)

となって、 p - q = 1 としてあげると  X が最大になる。つまり答えは

  •  X = A_{i} - B_{i}

これが実際に条件を満たすことは容易に確かめられる。

#include <iostream>
#include <set>
using namespace std;
using pint = pair<int,int>;

int main() {
    int N;
    cin >> N;
    set<pint> se;
    for (int i = 0; i < N; ++i) {
        long long a, b;
        cin >> a >> b;
        if (a == b) cout << -1 << endl;
        else cout << max(a, b) - min(a, b) << endl;
    }
}