西格玛函数σ 线性筛求约数和

西格玛函数σ 线性筛求约数和

​​ 解法：待填坑

其实这个完全可以拓展到线性筛求积性函数

因为非完全积 所以在两数不互质的情况下不可以直接相乘

但是两数互质的情况下就可以直接相乘

下面需要讨论下不互质的情况 我设定一个数组min_factory_a表示我这个数的最小质因子乘起来是多少 因为非完全积性，那么其实我们每次枚举到i%prime[j]==0的时候就是因为这个prime[j]（仔细考虑线性筛）的出现会导致答案有所不同 于是我们想办法把这部分的贡献都除掉 然后再乘以这部分+新的prime[j]后生成的新的贡献就可以了

#include#define N 110000000int sigma[N],min_factory_a[N],prime[N/10],not_prime[N],n; int main(){ freopen("ex1.in","r",stdin); freopen("ex1.out","w",stdout); scanf("%d",&n);sigma[1]=1;int top=0; for (int i=2;i<=n;++i){ if (!not_prime[i]){ sigma[i]=i+1;prime[++top]=i;min_factory_a[i]=i; } for (int j=1;prime[j]*i<=n;++j){ not_prime[prime[j]*i]=1; if (i%prime[j]==0){ if (i*prime[j]==min_factory_a[i]*prime[j]) sigma[i*prime[j]]=sigma[i]+prime[j]*i;else sigma[i*prime[j]]=sigma[i]/sigma[min_factory_a[i]]*sigma[min_factory_a[i]*prime[j]]; min_factory_a[i*prime[j]]=min_factory_a[i]*prime[j]; break; }sigma[i*prime[j]]=sigma[i]*(prime[j]+1); min_factory_a[i*prime[j]]=prime[j]; } } for (int i=1;i<=n;++i) printf("%d\n",sigma[i]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。