024号文書

主にプログラミング

ABC112 D - Partition

ABC

問題

ABC112 D- Partitionです。

解法

求める解を $g$ とすると、

$a_1 = g b_1$
$a_2 = g b_2$
...
$a_N = g b_N$

のように表せます。

$a_1 + a_2 + \cdots a_N = M$ より、 $g(b_1 + b_2 + \cdots + b_N) = M$ が成り立ちます。したがって、 $g$ は $M$ の約数です。

$a_1, a_2, \ldots, a_N \geq 1$ より、 $b1, b2, \ldots, b_N \geq 1$ です。したがって、 $M = g(b_1 + b_2 + \cdots + b_N) \geq gN$ 、すなわち、 $g \leq M/N$ が成り立ちます。

以上より、以下を満たす最大の整数 $g$ を求めればよいです。

$g$ は $M$ の約数である
$g \leq M/N$

ACしたコード

from math import sqrt

N, M = map(int, input().split())
ans = max(M // i if M // i <= M / N else i  for i in range(1, int(sqrt(M)) + 1) if M % i == 0 and i <= M / N)
print(ans)