AtCoder Beginner Contest 136：E - Max GCD

問題

https://atcoder.jp/contests/abc136/tasks/abc136_e

解法

最終的な答えを g，操作後の A_i の値を a_i とすると，a_i % g == 0 であるから，(a_1 + a_2 + ... + a_N) % g == 0 であり，A 全体の総和は操作によって変化しないから，(A_1 + A_2 + ... + A_N) % g == 0 である．よって，g の候補は A の和の約数になる．

次に，各候補が答えとなりうるかどうかを調べていく．A_i を g で割った余りを r_i とおく．このとき，A_i を -r_i するか +(g - r_i) するかの 2 通りがあり，操作による変化量 d_i の和は 0 でなければならない（操作で全体の和は変わらないので）．実は，r_i を昇順にソートし，前からいくつかを d_i = -r_i とし，残りを d_i = (g - r_i) とすることで d_i の和を 0 にすることができる g が存在する．これは r_i と (g - r_i) を累積和で持っておくことで O(1) で d_i の和が 0 となるかを調べることが出来る．全体で O(sqrt(A_max) * NlogN)．

解答

https://atcoder.jp/contests/abc136/submissions/7664114