euler1
int euler(int n)
{
int res=n,a=n;
for(int i=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);
return res;
}
euler2
int phi[maxn+5];
void euler()
{
phi[1]=1;
for(int i=2;i phi[i]=i; for(int i=2;i if(phi[i]==i) for(int j=i;j phi[j]=phi[j]/i*(i-1); } euler3 int phi[maxn+5],prime[maxn+5],cnt; bool notp[maxn+5]; void getphi() { phi[1]=1,cnt=0; for(int i=2;i<=maxn;i++) { if(!notp[i]) { prime[++cnt]=i; phi[i]=i-1; } for(int j=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; } else phi[i*prime[j]]=phi[i]*(prime[j]-1); } } } ©著作权归作者所有：来自51CTO博客作者qinXpeng的原创作品，如需转载，请注明出处，否则将追究法律责任
