ベスパリブ

ベスパもってないです。バイク買いました。

ABC 112: D問題の解説 (Python3)

問題:AtCoder Beginner Contest 112: D - Partition

公式解説PDF:https://img.atcoder.jp/abc112/editorial.pdf

公式解説動画:AtCoder Beginner Contest 112 解説放送 - YouTube

解説

解説動画まんまです。


 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()

計算量は O(\sqrt{M})です 。