Max GCD 2 [第二回日本最強プログラマー学生選手権 C]

https://atcoder.jp/contests/jsc2021/tasks/jsc2021_c

解説

https://atcoder.jp/contests/jsc2021/submissions/21830976

問題で要求されているx,yを全列挙する方針は10¹⁰通りを超えてしまうのでこれはできない。
何か別の視点で考えることはできないか。

答えの候補を全探索する

gcd(x,y)はx,y以下に必ずなるので、答えの方を考えてみると大体2×10⁵が上限になる。
（もうちょっと小さくなるけど誤差として考えない）
これは全探索できる。
よって、答えの候補を全探索して、高速に判定することで答えを求めることにしよう。

判定問題

この判定問題は倍数の個数を使うことで実現できる。
gcd(x,y)=gかつA≦x＜y≦Bを満たすx,yの組が存在するかを判定するために
「[A,B]にgの倍数が2つ以上存在する」ことを利用する。
もしかしたら正確な条件ではないのかもしれないが、連続する2つの数は素数であるから連続するgの倍数の数を取ってきたらgcdはgになるはず
（未証明！）

よって、[A,B]にgの倍数がいくつあるかが分かれば判定ができるようになった。
これはB/g-(A-1)/gで求めることができる。
B/gで[1,B]にあるgの倍数の個数を求めることができ、(A-1)/gで[1,A-1]にあるgの倍数の個数を求めることができるためである。
このような区間の個数を始点から（今回であれば1から）の計算に帰着させる方法は汎用的に使用できるので覚えておこう。

int A, B;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B;

    int ans = 1;
    rep(gcd, 1, 201010) {
        int cnt = B / gcd - (A - 1) / gcd;
        if (2 <= cnt) ans = gcd;
    }
    cout << ans << endl;
}