欧拉函数,欧拉定理,费马小定理介绍及模板

欧拉函数总结

介绍

欧拉函数的定义:对于正整数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);  
}  
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注