Luogu3708 - Click Here
Description
Koishi在Flandre的指导下成为了一名数学大师，她想了一道简单的数学题。
输入一个整数n，设$f(x)=\sum_{i=1}^n x~mod~i$，你需要输出$f(1),f(2)…f(n)$。
按照套路，Koishi假装自己并不会做这道题，就来求你帮忙辣。
Input
一个正整数n。
对于100%的数据，$1 \leq n \leq 10^6$。
Output
一行用空格分隔的n个整数$f(1),f(2)…f(n)$。
Solutions
今天的模拟赛做了一道调和级数的题，然后就想起这题了233。
首先易发现$x\,mod\,a$($a$为定值)的变化一定是$0,1,2…a-1,0,1,2…a-1…$这样循环的。
再观察$x \, mod \, a \, - \, x$的变化，它变成了$0,0,0…a,a,a…2a,2a,2a…$。即在$a$的倍数位置差值增加$a$。
因此，对于此题，只需要对于每个模数$i$都在对应位置累计差值，然后跑一遍前缀和即可得到答案。
时间复杂度$\sum \frac{n}{i}=O(nlogn)$
CODE
CODE - Click Here