筛约数个数和
理论基础：
1、对n质因数分解，n=p1^k1 * p2^k2 * p3^k3 ……
则n的约数个数为(k1+1)*(k2+1)*(k3+1)……
2、线性筛素数时，用i和素数pj来筛掉 i*pj，
其中pj一定是i*pj的最小素因子
如果i是pj的倍数，pj也是i的最小素因子
设t[i] 表示i的约数个数，e[i] 表示i的最小素因子的个数
A、如果i是质数，t[i]=2,e[i]=1
B、如果i不是质数，枚举已有的质数pj
i*pj的最小素因子是pj
1、如果i是pj的倍数那么e[i]即为i中包含的pj的个数，所以i*pj中包含的pj的个数为e[i]+1
所以e[i*pj]=e[i]+1,t[i*pj]=t[i]/(e[i]+1)*(e[i]+2)
2、如果i不是pj的倍数，e[i*pj]=1,t[i*pj]=t[i]*t[pj]（积性函数的性质）=t[i]*2（素数的约数个数=2）
1 #include2 3 using namespace std; 4 5 #define N 1000001 6 7 bool vis[N]; 8 int prime[N]; 9 10 int t[N],e[N];11 12 int main()13 {14 int n;15 scanf("%d",&n);16 int cnt=0;17 t[1]=1;18 for(int i=2;i<=n;++i)19 {20 if(!vis[i])21 {22 prime[++cnt]=i;23 t[i]=2;24 e[i]=1;25 }26 for(int j=1;j<=cnt;++j)27 {28 if(i*prime[j]>n) break;29 vis[i*prime[j]]=true;30 if(i%prime[j]==0)31 {32 t[i*prime[j]]=t[i]/(e[i]+1)*(e[i]+2);33 e[i*prime[j]]=e[i]+1;34 break;35 }36 else 37 {38 t[i*prime[j]]=t[i]*2;39 e[i*prime[j]]=1;40 }41 }42 }43 long long ans=0;44 for(int i=1;i<=n;++i) ans+=t[i];45 printf("%lld",ans);46 }
筛约数和
t[i] 表示i的约数和
e[i] 表示i的约数中，不能被i的最小素因子整除的约数和
A、i是质数，t[i]=i+1,e[i]=1
B、i不是质数
i*pj的最小素因子是pj
1、如果i不是pj的倍数，那么i的所有约数中，必然没有pj的倍数
可以用反证法证明这个：设x是i的约数，且x是pj的倍数，
那么 x=pj*b，i=x*a=pj*b*a
即i是pj的b*a倍，与i不是pj的倍数相矛盾
令S表示i的约数集，S’表示i的约数翻pj倍后的数的集合
则S∩S’=∅，则S和S’中无重复元素
所以t[i*pj]=S+S'=t[i]+t[i]*pj=t[i]*(pj+1)
S’中的所有元素都能整除pj，所以e[i*pj]=t[i]
2、如果i是pj的倍数，那么S和S’必有交集T
T=S中pj的倍数
所以i*pj的约数和要去除交集T
那么t[i*pj]=S+S'-T=S'+S-T=t[i]*pj+e[i]
因为pj既是i的最小素因子，有事i*pj的最小素因子
所以e[i*pj]=e[i]
1 #include2 3 typedef long long LL; 4 5 #define N 100001 6 7 int prime[N]; 8 bool vis[N]; 9 10 LL t[N],e[N];11 12 int main()13 {14 int n;15 scanf("%d",&n);16 int cnt=0;17 for(int i=2;i<=n;++i)18 {19 if(!vis[i])20 {21 prime[++cnt]=i;22 t[i]=i+1;23 e[i]=1;24 }25 for(int j=1;j<=cnt;++j)26 {27 if(prime[j]*i>n) break;28 vis[prime[j]*i]=true;29 if(i%prime[j]==0)30 {31 t[i*prime[j]]=t[i]*prime[j]+e[i];32 e[i*prime[j]]=e[i];33 break;34 } 35 t[i*prime[j]]=t[i]*(prime[j]+1);36 e[i*prime[j]]=t[i];37 }38 }39 LL ans=0;40 for(int i=1;i<=n;++i) ans+=t[i];41 printf("%lld",ans);42 }
参考博客：
百度百科