ABC172 D - Sum of Divisors (400)
$ O(N \log N)
は
$ N=10^7
なので間に合わなそう
$ i
が約数として使われる回数は
$ N/i
で出せる
$ i
を約数にするのは連続した
$ i
の倍数達なので、使われる回数を
$ j
とすると、ここで加算すべきなのは
$ \frac{i j (j+1)}{2}
2からNまでで上を求めれば良いので
$ O(N)
問題:
https://atcoder.jp/contests/abc172/tasks/abc172_d
提出:
https://atcoder.jp/contests/abc172/submissions/14743267
#ABC172
#400pt
#D
#ABC
#AtCoder
#O(N)