読者です 読者をやめる 読者になる 読者になる

Educational Codeforces #20 C: Maximal GCD

a[1]~a[k]のGCDをgとする。

g | a[i]なので
b[i] = a[i]/g
のような数列bを定められる。(b[i]>=1)
Σa[i] = n
より
gΣb[i] = n
g | n
よって
gの候補はnの約数のみ。すべて試す。
総和を考慮せずに、とりあえず一番和の小さい数列を作ると
a[i]=gi
その和は
Σgi
=gΣi
=gi*(i+1)/2
これはn以下でなければならないから、
gk*(k+1)/2<=n
逆にこのとき、
足りないn-gi(i+1)/2 をa[k]に加えればよい。