jsc2021 C問題 Max GCD 2 で恥ずかしいミス

第二回日本最強プログラマー学生選手権(jsc2021) のC問題を解説しつつ、
恥ずかしいミスをしてしまったので、自戒をこめてここに残しておきます。

atcoder.jp

問題の概要

AとBが与えられて、となるxとyの最大公約数の最大値を求める問題です。
なので、AからBの範囲で全ての組み合わせでgcdを求めようとすると、
組み合わせを考えようとした段階で計算量は億を簡単に超えるのでアウトです。

考え方

発想を転換して、答えとなる最大公約数をCと固定して、これがAからBの範囲で2つの数で割り切れればOKとします。
サラリと書いてますけど、ここに至るのにけっこう時間がかかったのも反省。。。

最大公約数の候補となるCのとりうる範囲はです。
1からBでループして、AからBの範囲で割り切れる数を数えます。
割り切れる数が2になったらすぐにループを抜けて、最大公約数の最大値を比較します。

以下のコードを書きました。

A, B = map(int, input().split())
ans = 0
for c in range(1, B + 1):
    count = 0
    for x in range(A, B + 1):
        if x % c == 0:
            count += 1
            if count == 2:
                count = 0
                ans = max(ans, c)
                break
 
print(ans)

本当に恥ずかしい。。。

A〜Bの範囲で、Cで割り切れる数を求めるのに単純にループしたら、タイムアウトしますよ。。。

A〜Bの範囲でCで割り切れる数は、（1〜Bの範囲でCで割り切れる数）から（1〜(A-1)の範囲でCで割り切れる数）を引いた値です。。。

1〜Bの範囲でCで割り切れる数は、の余りを切り捨てた数です。
1〜Aの範囲でCで割り切れる数は、の余りを切り捨てた数です。

A, B = map(int, input().split())
ans = 1
for c in range(2, B + 1):
    count = B // c - ((A - 1) // c)
    if count >= 2:
        ans = max(ans, c)
print(ans)

かなり恥ずかしい。。。