题目链接
题意
输入一个整数\(n\)\((n\leq 1e6)\)，设\(f(x)=\sum_{i=1}^n x\mod i\)，你需要输出\(f(1),f(2)...,f(n)\).
输入输出格式
输入格式：
一个正整数n。
输出格式：
一行用空格分隔的n个整数\(f(1),f(2)...f(n)\).
输入输出样例
输入样例#1：
10
输出样例#1：
9 16 22 25 29 27 29 24 21 13
思路
列表
\i 1 2 3 4 5 6 7 8 9 10
x mod i\
x\
1 0 1 1 1 1 1 1 1 1 1
2 0 0 2 2 2 2 2 2 2 2
3 0 1 0 3 3 3 3 3 3 3
4 0 0 1 0 4 4 4 4 4 4
5 0 1 2 1 0 5 5 5 5 5
6 0 0 0 2 1 0 6 6 6 6
7 0 1 1 3 2 1 0 7 7 7
8 0 0 2 0 3 2 1 0 8 8
9 0 1 0 1 4 3 2 1 0 9
10 0 0 1 2 0 4 3 2 1 0
递推
在已经算出了\(f(x)\)的基础上，怎么得到\(f(x+1)\)呢？
因为$$(x+1)\mod i = ((x\mod i)+1)\mod i=
\begin{eqnarray}
\begin{cases}
(x\mod i)+1,&i\nmid (x+1)\cr
0, &i\mid (x+1)
\end{cases}
\end{eqnarray}$$
所以\(f(x+1)=f(x)+n-1-g(x+1)\)，\(n-1\)的含义为下一行比上一行每个多\(1\)，\(g(x+1)\)的含义为贡献本该算作\(0\)却算作了\(i\)因而多加了的部分，即\(\sum_{i\mid (x+1)}i\).
\(i=1\)的时候特殊处理一下。
线性筛
线性筛求一下约数和即可解决。
此处具体讲解可参见 积性函数的性质及证明 + 线性筛 ——Wubaizhe
Code
#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
typedef long long LL;
int prime[maxn], mx[maxn], sum[maxn], n, tot;
LL d[maxn], ans[maxn];
bool vis[maxn];
void init() {
d[1] = 0;
for (int i = 2; i <= n; ++i) {
if (!vis[i]) {
prime[tot++] = i;
d[i] = sum[i] = i+1;
mx[i] = i;
}
for (int j = 0; j < tot; ++j) {
if (prime[j] * i > n) break;
vis[prime[j] * i] = true;
if (i % prime[j] == 0) {
mx[i * prime[j]] = mx[i] * prime[j];
sum[i * prime[j]] = sum[i] + mx[i * prime[j]];
d[i * prime[j]] = d[i] / sum[i] * sum[i * prime[j]];
break;
}
mx[i * prime[j]] = prime[j];
sum[i * prime[j]] = prime[j] + 1;
d[i * prime[j]] = d[i] * d[prime[j]];
}
}
for (int i = 2; i <= n; ++i) --d[i];
}
int main() {
scanf("%d", &n);
init();
ans[1] = n-1; printf("%lld", ans[1]);
for (int i = 2; i <= n; ++i) {
ans[i] = ans[i-1] + n-1 - d[i];
printf(" %lld", ans[i]);
}
printf("\n");
return 0;
}