积性函数
1.利用欧拉筛求f(1),……,f(n)
//欧拉筛求f(1),……,f(n)
void euler{
f[1]=1;
for(int i=2;i<=n;i++){
if(!st[i]) p[++tot]=i,f[i]=calc_f(i,1);
for(int j=1;j<=tot&&i*p[j]<=n;j++){
st[i*p[j]]=true;
if(i%p[j]==0){
cnt[i*p[j]]=cnt[i]+1;//cnt[n]:表示n的最小的质因子出现的次数
f[i*p[j]]=f[i]/calc_f(p[j],cnt[i])*calc_f(p[j],cnt[i]+1);//对p[j]的出现次数进行一个修正
}
cnt[i*p[j]]=1;//i*p[j]的最小质因子为p[j],并且出现次数为1
f[i*p[j]]=f[i]*calc_f(p[j],1);
}
}
}
标签:筛求,积性,多项式,void,int,欧拉
From: https://www.cnblogs.com/mendax-Z/p/18188994