首页 > 代码库 > [常见积性函数的线性筛]【学习笔记】
[常见积性函数的线性筛]【学习笔记】
【欧拉函数】
φ(n)=n(1-1/p1)(1-1/p2)...(1-1/pk)
通过上式易发现 p[j]|i时 phi[i*p[j]]=phi[i]*p[j] 因为phi[i]的n是n*p[j]/p[j]，其他的部分一样
证明：http://www.cnblogs.com/candy99/p/6200660.html
void sieve(){ phi[1]=1; for(int i=2;i<=n;i++){ if(!vis[i]){ p[++m]=i; phi[i]=i-1; } for(int j=1;j<=m&&i*p[j]<=n;j++){ vis[i*p[j]]=1; if(i%p[j]==0){ phi[i*p[j]]=phi[i]*p[j]; break; } phi[i*p[j]]=phi[i]*(p[j]-1); } } for(int i=1;i<=n;i++) s[i]=s[i-1]+phi[i];}
【约数个数】
根据乘法原理，n的约数个数为∏{i=1...r}(ai+1)
由上式可得 p[j]|i时 facnum[i*p[j]]=facnum[i]/(minfac[i]+1)*(minfac[i*p[j]]+1)
【约数和】
n=p1^a1*p2^a2*…*pr^ar
则其约数和=∏{i=1...r}(Σ{j=1..aj}pi^j)
p[j]|i时，得到sumfac[i*p[j]]
需要除以Σ(p[j]^(0..minfac[i]))
再乘以Σ(pris[j]^(0..minfac[k])
其中minfac[k]=minfac[i]+1
这样开两个辅助数组记录
t1[i]=Σ(minfac[i]^(0..a[minfac[i]]))
t2[i]=mindiv[i]^a[minfac[i]]
int notp[N],p[N],mu[N],minfac[N],t1[N],t2[N],sf[N];
void sieve(){ mu[1]=1; sf[1].s=1; for(int i=2;i<N;i++){ if(!notp[i]){ p[++p[0]]=i,mu[i]=-1; minfac[i]=i; sf[i]=i+1; t1[i]=i+1; t2[i]=i; } for(int j=1,k;j<=p[0]&&(k=i*p[j])<N;j++){ notp[i*p[j]]=1; minfac[k]=p[j]; if(i%p[j]==0){ mu[i*p[j]]=0; t2[k]=t2[i]*p[j]; t1[k]=t1[i]+t2[k]; sf[k]=sf[i]/t1[i]*t1[k]; break; } mu[i*p[j]]=-mu[i]; t1[k]=1+p[j]; t2[k]=p[j]; sf[k]=sf[i]*sf[p[j]]; } }}
[常见积性函数的线性筛]【学习笔记】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。