欧拉函数
euler1
inteuler(intn){intres=n,a=n;for(inti=2;i*i<=a;i++){if(a%i==0){res=res/i*(i-1);while(a%i==0)a/=i;}}if(a>1)res=res/a*(a-1);returnres;}
euler2
intphi[maxn+5];voideuler(){phi[1]=1;for(inti=2;i<maxn;i++)phi[i]=i;for(inti=2;i<maxn;i++)if(phi[i]==i)for(intj=i;j<maxn;j+=i)phi[j]=phi[j]/i*(i-1);}
euler3
intphi[maxn+5],prime[maxn+5],cnt;boolnotp[maxn+5];voidgetphi(){phi[1]=1,cnt=0;for(inti=2;i<=maxn;i++){if(!notp[i]){prime[++cnt]=i;phi[i]=i-1;}for(intj=1;j<=cnt&&i*prime[j]<=maxn;j++){notp[i*prime[j]]=1;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}elsephi[i*prime[j]]=phi[i]*(prime[j]-1);}}}
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。