欧拉定理&欧拉函数

定义#

欧拉函数(Euler’s totient function),定义为中与互质的数的个数。
欧拉定理:

性质#

1. 要求与互质;

2. 设,那么
   ;

3. ;
   ;
   ;

4. 欧拉函数是积性函数:
   若,则

5. 设为的一个质因子，为的次数，则有成立

   • 证明：设，那么

计算#

1. 一种基于质因数分解求欧拉函数的算法(求单个)

   int phi(int x){
       int ret = x;
       int t=sqrt(x);
       for(int i =2;i<=t;i++){
           if(x%i==0){
               while(x%i==0)x/=i;
               ret = ret / i * (i - 1);
           }
       }
       if(x>1) ret=ret/x*(x-1);
       return ret;
   }

   cpp
2. 线性筛欧拉函数

    const int N = 1e6 + 10;
    int n, cnt;//cnt标记素数个数
    int phi[N];//存每个数的欧拉函数
    int prim[N];//存放素数
    bool vis[N];//判断是不是素数
    int ans;
   
    int getphi(int n){
        phi[1] = 1;
        for(int i = 2; i <= n; i++){
            if( !vis[i] ){
                prim[++cnt] = i;
                phi[i] = i - 1;
            }
            for(int j = 1; j <= cnt; j++){
                if(i * prim[j] > n) break;
                vis[i * prim[j]] = true;
                if(i % prim[j] == 0){
                    phi[i * prim[j]] = prim[j] * phi[i];break;
                }
                else{
                    phi[i * prim[j]] = phi[i] * (prim[j] - 1);
                }
            }
        }
        for(int i = 1; i <= n; i++){
            ans += phi[i];
        }
        return ans;
    }

   cpp

   code

应用#

用欧拉定理求逆元：;
特别的，若为质数：
快速幂即可

int powermod(int a, int b, int n){
    int ret = 1;
    while(b){
        if(b & 1) ret=(long long)ret*a%n;
        a=(long long)a*a%n;
        b>>=1;
    }
    return ret;
}