欧拉函数性质、证明及求法

定义

  • 欧拉函数φ(n)表示1~n中与n互质的数的个数
  • φ(n)=n(1-1/p1)(1-1/p2)(1-1/p3)......;其中p1、p2、p3…为n的质因数,n为正整数 ;
    比如x=12,其质因数为2,3。在1到12中,有1/2 的数是2的倍数,那么就有(1-1/2)的数不是2的倍数,
    及1,3,5,7,9,11;在这些数中,有1/2的数是3的倍数,那么就有(1-1/3)的数不是3的倍数,及1,5,7,11;
    这四个数即不是2的倍数,也不是3的倍数,故φ(12)=12*(1-1/2)*(1-1/3)=4

积性函数

若当m与n互质时f(mn)=f(m)f(n),那么f是积性函数。若对任意正整数,都有f(nm)=f(n)f(m)成立,则f是完全积性函数。

欧拉函数的重要性质

  • 对于质数p,φ(p)=p−1;
  • 若p为质数,n=p^k,则φ(n)=p^k-p^(k-1);
  • 欧拉函数是积性函数,但不是完全积性函数。若m,n互质,则φ(m*n)=φ(m)*φ(n)特殊的,当m=2,n为奇数时,φ(2n)=φ(n);
  • 当n>2时,φ(n)是偶数;
  • 小于n的数中,与n互质的数的总和为:φ(n)*n / 2 (n>1);
  • n的因数(包括1和它自己)的欧拉函数之和等于n
  • 设p为质数,若p|n且p^2|n,则φ(n)=φ(n/p)*p
  • 设p为质数,若p|n但n%p^2!=0,则φ(n)=φ(n/p)*(p-1)

性质证明

截自https://blog.csdn.net/liuzibujian/article/details/81086324

求法

  • 直接使用公式求一个数n的欧拉函数值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    LL phi(LL n){//欧拉函数 
    LL i,rea=n;
    for(i=2;i*i<=n;i++){
    if(n%i==0){
    rea=rea-rea/i; //res=res*(1-(1/i))
    while(n%i==0) n/=i;
    }
    }
    if(n>1) rea=rea-rea/n; //res=res*(1-(1/n)) 最后一个质因数
    return rea;
    }
  • 使用埃拉托斯特尼筛法
    φ(n)=n(1-1/p1)(1-1/p2)....(1-1/pk),其中p1、p2…pk为n的所有素因子。
    比如:φ(12)=12*(1-1/2)*(1-1/3)=4
    利用这个就比较好求了,可以用类似求素数的筛法。
    先筛出N以内的所有素数,再以素数筛每个数的φ值。
    比如求10以内所有数的φ值:
    设一数组phi[11],赋初值phi[1]=1,phi[2]=2…phi[10]=10;
    然后从2开始循环,把2的倍数的φ值 *(1-1/2),则phi[2]=2*(1/2)=1,phi[4]=4*(1/2)=2,phi[6]=6*(1/2)=3....;
    再是3,3的倍数的φ值*(1-1/3),则phi[3]=3*(2/3)=2,phi[6]=3*(2/3)=2,phi[9]=.....;
    再5,再7…因为对每个素数都进行如此操作,因此任何一个n都得到了φ(n)=n(1-1/p1)(1-1/p2)....(1-1/pk)的运算

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void Init(int Max){   
    phi[1]=1;
    for(int i=2;i<Max;i++)
    phi[i]=i;
    for(int i=2;i<Max;i++)
    if(phi[i]==i)
    for(int j=i;j<Max;j+=i)
    phi[j]=phi[j]/i*(i-1); //先进行除法是为了防止中间数据的溢出
    }
Donate comment here