第一种:
LL Eular(LL n) { LL fac,ans=1; for(fac=2;fac*fac<=n;fac++) { if(n%fac==0) { n/=fac; ans*=fac-1; while(n%fac==0) { n/=fac; ans*=fac; } } } if(n>1) ans*=n-1; return ans; }
第二种
const int MAXN = 10001; LL phi[MAXN]; void GetPhi() { LL i,j; for(i=1;i<MAXN;i++) phi[i]=i; for(i=2;i<MAXN;i++) { if(phi[i]=i) { for(j=i;j<MAXN;j+=i) phi[j]=phi[j]/i*(i-1); } } }