ARC126 C - Maximize GCD
考えたこと
今回は関係ないが、よくある最大公約数の性質として
gcd(A1, A2, ... , An) | sum(A1, A2, ... , An)となる
似た問題で何回かi, jを選びA[i]++, A[j]--としたうえでの最大公約数を最大化するものがあったが、それにはこの性質が使えた
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
今回はg>=max(A)で全ての数をgに出来るなら答えはg以上なので
それが実現できないg < max(A)の場合について考える
まず、各iについてAiをgの倍数にするのに必要な操作回数は
(Ki-1)g < Ai <= Ki*gを満たすKiで
Ki*g-Ai回となる
またここで重要な事として、gを定めた時のK1,K2...,Knの値は最大でもmax(A) / g程度である
(なぜなら(Ki-1) * g < Ai <= max(A)より、(Ki-1) <= max(A)/gだから)
よってありえる(g, K)の組は調和級数でO(max(A) log(max(A)))個であり
Aを昇順にソートして、gについてKが同じであるようなi~jの範囲を調べるのO(log N)使ったとしても計算量は全体でO(max(A) log(max(A)) log(N))
------------------------------------------------------------------------------------
感想
gとKのペアに注目すれば、Kはg*K <= 上限の範囲だけ見ればいい形になっているので調和級数だという事に気づければよかった
