欧拉函数总结

介绍

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

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

定理：

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

以下是两个常用的定理:

• 欧拉定理:对于正整数$a,m$（$m\ge 2$）且 $a$ 与 $m$ 互质（$gcd(a,m)=1$），有$a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$
• 费马小定理: 当$m$是质数且$m\nmid a$（即$gcd(a,m)=1$）时，$a^{m-1}\equiv 1(\mathrm{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;  
}

时间复杂度 $O(\sqrt{n})$。

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

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

时间复杂度 $O(N\log \log N)$。

线性筛法求欧拉函数:

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]]，利用了欧拉函数的积性
        }
    }
}

时间复杂度 $O(N)$。