解説

解説動画まんまです。

$a_1 + a_2 + ... + a_N = M$ のとき、最大公約数 $gcd(a_1, a_2, ..., a_N)$ の最大値は？という問題です。

ここで $gcd(a_1, a_2, ..., a_N) = K$ とおくと、

$a_1, a_2, ... , a_N$ はそれぞれKの倍数なので、MもKの倍数です。

MがKの倍数ということは、KはMの約数ということです。

KはMの約数ということは、 $M \geq K N$ と書けます。

たとえば、N=10, M=168のときの、約数Kの最大値を求めたいとします。

Mの約数は1, 2, 3, 4, 6, 7, 8, 12, 14, 21, 24, 28, 42, 56, 84, 168です。

K = 1のとき

$M = 9K + 159K$ となるのでOKです。

K = 7のとき

$M = 9K + 15K$ となるのでOKです。

K = 8のとき

$M = 9K + 12K$ となるのでOKです。

K = 12のとき

$M = 9K + 5K$ となるのでOKです。

K = 14のとき

$M = 9K + 3K$ となるのでOKです。

K = 21のとき

$M = 9K - 21$ で、9KはM=168の値を超えてしまうのでだめです。

K=24以降も、同様に9KがMを超えてしまうのでだめです。

以上の考察から、Mの約数Kのうち、 $M \geq K N$ を満たす最大のKを探索すれば良いです。

制約より、Mのとりうる最大値は $10^9$ と大きいですが、 $M=AB$ としたときの約数のペア(A, B)は高々 $\sqrt{M}$ を境に対称なので、探索は $\sqrt{M}$ 以下までで十分です。

対称というのはたとえば、M=100のとき、約数のペア(A, B)は、

M = 1 * 100
M = 2 * 50
M = 4 * 25
M = 5 * 20
M = 10 * 10 (ここから対称)
M = 20 * 5
M = 25 * 4
M = 50 * 2
M = 100 * 1

となるので、約数のペアを探すのに1~100まで探索しなくても、1~10までの探索でOKです。

コーナーケース

特になし

実装

def solve():
    N, M = list(map(int, input().split()))

    # Mの約数をすべて調べる
    divs = set()  # Mの約数を格納する
    n = 1
    while n <= M**(1/2):
        if M%n == 0:
            # nがMの約数ならば
            divs.add(n)
            divs.add(M//n)
        n += 1

    # Mの約数dの中で、M >= d*Nを満たす最大のものが答え
    ans = 0
    for d in divs:
        if M >= d*N:
            ans = max(ans, d)
    print(ans)


if __name__ == "__main__":
    solve()