线性筛约数和函数

挺麻烦的，就当存一下板子了

#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 1000005
#define re register
#define LL long long
int n;
int f[maxn],p[maxn],s[maxn],d[maxn],num[maxn];
int main()
{
    std::cin>>n;
    s[1]=f[1]=1;
    for(re int i=2;i<=n;i++) {
        if(!f[i]) p[++p[0]]=i,s[i]=i+1,num[i]=1+i,d[i]=i;
        for(re int j=1;j<=p[0]&&p[j]*i<=n;j++) {
            f[p[j]*i]=1;
            if(i%p[j]==0) {
                d[p[j]*i]=d[i]*p[j];
                num[p[j]*i]=num[i]+d[p[j]*i];
                s[p[j]*i]=s[p[j]*i/d[p[j]*i]]*num[p[j]*i];
                break;
            }
            s[p[j]*i]=s[i]*s[p[j]];
            d[p[j]*i]=p[j];
            num[p[j]*i]=1+p[j];
        }
    }
    for(re int i=1;i<=n;i++) printf("%d\n",s[i]);
    return 0;
}

线性筛约数和函数

原文：https://www.cnblogs.com/asuldb/p/10368743.html