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);}}}