ABC136 E - Max GCD

f:id:tkr987:20200325023642p:plain

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

diff1600を超えると数学的素養がないと考察を進めるのが厳しい。

理解はしたけど一生出来るようにならないという気分になった。

各操作をしても合計は不変
答えMは $\sum A_{i}$ の約数
約数の個数は対数程度に収まる
剰余を0かMにする操作を調べる
a-b=(M-X)-(M-Y)=Y-X

まず、文章を読んで気になる点として、各操作をしても合計が変わらないという事が挙げられる。各操作をすることで数列 $A_{i}$ が $A'_{i}$ に変わったとき、割り切れる答えをMとすると全ての $A'_{i}=c_{i}M$ なので $\sum A'_{i}=CM=\sum A_{i}$ となる。すなわち、答えMは $\sum A_{i}$ の約数となる。約数の個数は $log{NA}$ 程度になる。高度合成数を参照。

https://ja.wikipedia.org/wiki/%E9%AB%98%E5%BA%A6%E5%90%88%E6%88%90%E6%95%B0

f:id:tkr987:20200330153758p:plain

次に、「各操作をしてMで割り切れる」という処理をするために各Aiの剰余を取っておく。この剰余を0かMにしたとき「全てのAiがMで割り切れる」ということであり、どのように矢印を選んでも各Aiの剰余を0またはMにする限り「全てのAiがMで割り切れる」ということになる。各操作は+1と-1がセットなので下矢印と上矢印の合計が一致してなければならず、そういう条件を満たす矢印の長さとKを比較すれば良い。Aiの剰余の合計と○倍のMが等しいので「剰余をソートして左側を0にして右側○個をMにするような組み合わせを全て試す」という処理をする。

下矢印と上矢印が交互に現れる場合、 $a-b=(M-X)-(M-Y)=Y-X$ なので入れ替えても矢印の合計は変わらない。そういう組み合わせは枝刈りすることが出来るため、計算量が $O(N\log{NA})$ に収まる。