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

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

問題へのリンク

問題概要

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

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

制約

• 

考えたこと

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

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

• 
• 

と書いてみると、一般性を失わずに として

• 

となって、 としてあげると が最大になる。つまり答えは

• 

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

#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;
    }
}