题解 P3708 【koishi的数学题】

· · 题解

看了一眼题解,复杂度是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)

#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;
}