ABC112 D - Partition - ツバサの備忘録

問題
 提出コード
$a_1,a_2, ... a_n$ の公約数を $p$ とします。
このとき、 $a_i$ は $p$ で割り切れるので、 $m$ も $p$ で割り切ることができます。
ということで、まず解の候補が $m$ の約数であることがわかります。これは、 $\sqrt{m}$ までを全探索して、それを $m$ で割ったときのあまりが0かどうかで判断すればよいです。 $p$ が $m$ の約数のとき、 $m/p$ も $m$ の約数であることに気を付ければ、約数を探索するのは $O(\sqrt{m})$ になります。
次に、 $p$ が問題の条件を満たすかどうかについて考えると、
すくなくとも $n$ 個の要素すべてが $p$ の倍数でなくてはなりません。このとき必要な最小値は、 $a_i$ がすべて $p$ であった場合ですので、 $m = p×n$ である必要があります。
しかし、 $m-p×n$ はかならず $p$ の倍数になっているため、残った数はどこか1つの要素にすべて放り込んでしまえばいいので、 $m \geqq p×n$ が成り立っていればよいことがわかります。
ということで、
$p$ は $m$ の約数、かつ $m \geqq p×n$ がなりたつ $p$ のうち最大のものを、 $O(\sqrt{m})$ の全探索によって求めれば、それが答えになります。