欧拉函数学习小记

（1）什么是欧拉函数？一个数n的欧拉函数一个数f(n)，表示[1,n-1]中与n互质的数的个数。比如f(2)=1,f(3)=2,f(4)=2。

（2）怎么求一个数n的欧拉函数?设p1,p2……pk是n的k个质因数，f(n)=n*(1-1/p1)*……(1-1/pk)。比如n=12,则p1=2,p2=3，那么f(12)=12*(1-1/2)*(1-1/3)=4。

（3）若k,m互质，则有：k^f(n)%n=1。如k=2,n=7,f(7)=6,2^6%7=1。

//求n的欧拉函数
int Euler(int n)
{
    int i,ans=n;
    for(i=2;i*i<=n;i++) if(n%i==0)
    {
        ans=ans/i*(i-1);
        while(n%i==0) n/=i;
    }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}

//求1到MAX的所有数的欧拉函数
const int MAX=5000005;
i64 f[MAX];

void init()
{
    int i,j;
    f[1]=1;
    for(i=2;i<MAX;i++) if(!f[i]) for(j=i;j<MAX;j+=i)
    {
        if(!f[j]) f[j]=j;
        f[j]=f[j]/i*(i-1);
    }
}