第二回日本最強プログラマー学生選手権 C Max GCD 2
整数
$ x
を固定する. すると
$ y = x + (xの約数)
とするのが最適となる. よって
$ x
の約数を全列挙し, そのおのおのについて試していけばよい. 計算量は
$ O(A max(\max (d(i) | A \leq i < B), \sqrt B))
となり, ギリギリ間に合う.
実装例:
https://atcoder.jp/contests/jsc2021/submissions/21808031