欧拉函数总结

介绍

欧拉函数的定义：对于正整数$n$，欧拉函数是小于等于$n$的数中，与$n$互质的数的数目

欧拉函数又称$\phi$函数，例如$\phi(8)=4$,因为1,3,5,7均和8互质

定理：

1. 如果$n$为某一个素数$p$，则:$\phi(p)=p-1$
2. 如果$n$为某一个素数$p$的幂次$p^a$，则:$\phi(p^a)=(p-1)*p^{a-1}$
3. 如果$n$为任意两个互质的数$a,b$的乘积，则:$\phi(a*b)=\phi(a)*\phi(b)$
4. 设$n=p_1^{a_1}*p_2^{a_2}*...*p_k^{a_k}$为正整数$n$的素数幂分解，那么 $\phi(n)=n*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})*...*(1-\frac{1}{p_k})$ 推论: 当$n$为奇数时，有$\phi(2n)=\phi(n)$

以下是两个常用的定理:

• 欧拉定理:对于任何两个数值的正整数$a,m$(m>=2)，有$a^{\phi(m)}\equiv 1(mod\ m)$
• 费马小定理: 当$m$是质数时，$a^{m-1}\equiv1(mod\ m)$

模板

返回小于等于n且与n互质的数的个数

int euler_phi(int n)  
{  
    int res = n;  
    int m = (int)sqrt(n);  
    for(int i = 2; i <= m; i++)  
        if(n % i == 0)  
        {  
            res = res / i * (i-1);  
            while(n % i == 0) n /= i;  
        }  
    if(n > 1) res = res / n * (n-1);  
    return res;  
}

筛选法求欧拉函数(比较慢)

void euler_phi()  
{  
    for(int i = 1; i < N; i++) phi[i] = i;  
    for(int i = 2; i < N; i++)  
        if(phi[i] == i) //成立说明i是素数
            for(int j = i; j < N; j += i) //j要从i开始，这样可以处理素数的情况  
                phi[j] = phi[j] / i * (i-1);  
}

线性筛法求欧拉函数:

int phi[N+10],prime[N+10],tot,ans;
bool mark[N+10];
void getphi()
{
    int i,j;
    phi[1]=1;
    for(i=2; i<=N; i++) //相当于分解质因式的逆过程
    {
        if(!mark[i])
        {
            prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。
            phi[i]=i-1;//当 i 是素数时 phi[i]=i-1
        }
        for(j=1; j<=tot; j++)
        {
            if(i*prime[j]>N)  break;
            mark[i*prime[j]]=1;//确定i*prime[j]不是素数
            if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else  phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性
        }
    }
}