C - Maximize GCD Editorial
by 
maspy
\(\max\{A_1, \ldots, A_N\}\) を \(A_{\max}\) と書くことにします。
◆ 問題の言い換え
一般に、\(x = \gcd(A_1, \ldots, A_N)\) という条件と比べて、\(x \mid \gcd(A_1, \ldots, A_N)\) という条件の方が扱いやすいです。後者の条件は、\(\forall i, x\mid A_i\) という要素ごとの条件に分解できるためです。
そこで、本問題の代わりに次の問題を解くことにします。
操作後に \(x\mid \gcd(A_1, \ldots, A_N)\) が成り立つようにできるような \(x\) の最大値を求めよ。
このように言い換えても、問題の答えは変わらないことは容易に確かめられます。
\(x\mid \gcd(A_1, \ldots, A_N)\) つまり、すべての \(A_i\) を \(x\) の倍数にするために必要な操作回数の最小値を \(\text{cost}(x)\) と書くことにします。
◆ \(\text{cost}(x)\) の計算
\(\text{cost}(x)\) は、各 \(A_i\) を \(x\) の倍数にするために必要な操作回数の総和です。
\(k\) を整数として、\((k-1)x < A_i \leqq kx\) となる \(A_i\) に対する操作回数をまとめて計算しましょう。この範囲の \(A_i\) に対して、操作回数は \(kx - A_i\) ですから、その総和は \(\sum_i (kx - A_i) = \sum_i kx - \sum_i A_i\) となります。つまり、
- \((k-1)x < A_i \leq kx\) となる \(i\) の個数を \(c\)
- \((k-1)x < A_i \leq kx\) となる \(i\) に対する \(A_i\) の総和を \(s\)
とすると、この範囲の \(A_i\) に対する操作回数の総和は \(kxc - s\) となることが分かります。累積和の事前計算をしておくことで、この値は \(O(1)\) 時間で計算することができます。
\(k\) を動かして和をとることで、\(\text{cost}(x)\) は \(O(\lceil A_{\max} / x\rceil)\) 時間で計算することができます。
◆解法まとめ
まず、上で述べた \(\text{cost}(x)\) の計算を \(1\leqq x\leqq A_{\max}\) に対して行います。 累積和の事前計算に \(O(N + A_{\max})\) 時間、\(\text{cost}(x)\) の計算に合計で \(O(\sum_{1\leq x\leq A_{\max}} \lceil A_{\max} / x\rceil)\) 時間となりますが、\(\sum_{1\leq x\leq A_{\max}} \lceil A_{\max} / x\rceil = O(A_{\max}\log A_{\max})\) であるため、ここまでの計算は合計 \(O(N + A_{\max}\log A_{\max})\) 時間で行えます。
ここまでで、\(x \leqq A_{\max}\) の範囲では、すべての \(A_i\) を \(x\) の倍数にすることが可能であるかはすべて判定できました。あとは \(x > A_{\max}\) の場合が残っていますが、この場合には \(\text{cost}(x) = Nx - \sum_i A_i\) が成り立つため、\(\text{cost}(x)\leqq K\) が成り立つような \(x\) が存在するかを判定し、存在する場合にその最大値を求めることは容易です。
以上により、本問題は全体として \(O(N + A_{\max}\log A_{\max})\) 時間で解くことができます。
◆ 解答例
posted:
last update: