题解 P3708 【koishi的数学题】
Zoewilly
2017-04-17 07:11:29
看了一眼题解，复杂度是nlogn的，不过我觉得如果数据大点会被卡掉
说一下我的做法：
考虑一下递推，考虑每一行和下一行的关系 比如说：
8%1 8%2 8%3 8%4 8%5 8%6 8%7 8%8 8%9 8%10 --------> f[8]
9%1 9%2 9%3 9%4 9%5 9%6 9%7 9%8 9%9 9%10 --------> f[9]
考虑一下f[8]和f[9] 的大小关系，可以发现，对于有些对应项,(9%1)=(8%1)+1,,,(9%2)=(8%2)+1........
但对于有些对应项 9%3=0 8%3=2
由于相邻两个数是互质的，他们不会有大于1的最大公约数，即不会出现x>1，使得8%x=0 && 9%x=0
所以对于9的因数x(x>1), a[9,x]=a[8,x]-(x-1);
所以f[9]=f[8]+10-(9的因数和)
推广： 对于f[x],f[x-1],在模(1....p)意义下,f[x]=f[x-1]+p-(x的因数和)
所以递推公式就出来了，边界条件f[1]=p-1; 递推的时间复杂度为O(N)
因数和怎么处理呢？已知因数和是积性函数（由积性函数定义可知），所以线性筛就可将其预处理，时间复杂度O(N)
综合一下，时间复杂度为O(N)
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1000000
typedef long long LL;
LL f[N+1],ans[N+1];
int prim[N+1],t[N+1],tot,n;
bool flag[N+1];
void init(void)//因数和线性筛
{
f[1]=1;
for (int i=2;i<=n;i++)
{
if (!flag[i])
{
prim[++tot]=i;
f[i]=i+1;
t[i]=i;
}
for (int j=1;j<=tot;j++)
{
int k=prim[j]*i;
if (k>n) break;
flag[k]=1;
if (i%prim[j]==0)
{
t[k]=t[i]*prim[j];
if (k==t[k])
for (int w=1;w<=k;w*=prim[j]) f[k]+=w;
else
f[k]=f[t[k]]*f[k/t[k]];
break;
}
t[k]=prim[j];
f[k]=f[prim[j]]*f[i];
}
}
}
int main()
{
scanf("%d",&n);
init();
ans[1]=n-1;
for (int i=2;i<=n;i++) ans[i]=ans[i-1]+n-f[i];
for (int i=1;i<=n;i++) printf("%lld ",ans[i]);
return 0;
}
```