事前に1~max(a[1],a[2],...,a[n])の約数を求めておく。次に、約数qをもつ数を数えてcnt[q]のように表す。部分列のgcdをgとしたときq|gを満たす空でない部分列を数えよう。これは簡単で、qを約数にもつ数すべてについて、部分列に含むかどうかを考えてcnt[q]^…

a[1]~a[k]のGCDをgとする。 g | a[i]なのでb[i] = a[i]/gのような数列bを定められる。(b[i]>=1)Σa[i] = nよりgΣb[i] = ng | nよってgの候補はnの約数のみ。すべて試す。総和を考慮せずに、とりあえず一番和の小さい数列を作るとa[i]=giその和はΣgi=gΣi=gi*(i…