欧拉函数总结

介绍

欧拉函数的定义:对于正整数nn,欧拉函数是小于等于nn的数中,与nn互质的数的数目

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

定理:

  1. 如果nn为某一个素数pp,则:ϕ(p)=p1\phi(p)=p-1
  2. 如果nn为某一个素数pp的幂次pap^a,则:ϕ(pa)=(p1)pa1\phi(p^a)=(p-1)*p^{a-1}
  3. 如果nn为任意两个互质的数a,ba,b的乘积,则:ϕ(ab)=ϕ(a)ϕ(b)\phi(a*b)=\phi(a)*\phi(b)
  4. n=p1a1p2a2...pkakn=p_1^{a_1}*p_2^{a_2}*...*p_k^{a_k}为正整数nn素数幂分解,那么 ϕ(n)=n(11p1)(11p2)...(11pk) \phi(n)=n*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})*...*(1-\frac{1}{p_k}) 推论: 当nn为奇数时,有ϕ(2n)=ϕ(n)\phi(2n)=\phi(n)

以下是两个常用的定理:

  • 欧拉定理:对于任何两个数值的正整数a,ma,m(m>=2),有aϕ(m)1(mod m)a^{\phi(m)}\equiv 1(mod\ m)
  • 费马小定理: 当mm是质数时,am11(mod 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]],利用了欧拉函数的积性
        }
    }
}

results matching ""

    No results matching ""