欧拉函数

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