欧拉函数 | 欧拉

原博客：https://blog.csdn.net/zxwsbg/article/details/81488956

φ(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1-1/pn)，其中pi为n的质因数

方法1：求单个数的欧拉函数

 1 long long eular(long long n) {
 2     long long ans = n;
 3     for(int i = 2; i*i <= n; i++)    {
 4         if(n % i == 0)        {
 5             ans -= ans/i; //等价于通项，把n乘进去
 6             while(n % i == 0) //确保下一个i是n的素因数
 7                 n /= i;
 8         }
 9     }
10     if(n > 1)ans -= ans/n;
11     //最后可能还剩下一个素因数没有除
12     return ans;
13 }

View Code

方法2：打表求欧拉函数

1 void euler()  {
2     for(int i=2; i<maxn; i++) {
3         if(!phi[i])          for(int j=i; j<maxn; j+=i) {
4                 if(!phi[j]) phi[j]=j;
5                 phi[j]=phi[j]/i*(i-1);
6             }
7     }
8 }

View Co

方法3：欧拉筛素数同时求欧拉函数

 1 void get_phi()  {
 2     int i, j, k;
 3     k = 0;
 4     for(i = 2; i < maxn; i++)      {
 5         if(is_prime[i] == false)          {
 6             prime[k++] = i;
 7             phi[i] = i-1;
 8         }
 9         for(j = 0; j<k && i*prime[j]<maxn; j++)          {
10             is_prime[ i*prime[j] ] = true;
11             if(i%prime[j] == 0)              {
12                 phi[ i*prime[j] ] = phi[i] * prime[j];
13                 break;
14             }              else              {
15                 phi[ i*prime[j] ] = phi[i] * (prime[j]-1);
16             }
17         }
18     }
19 }

View Code

欧拉函数的性质：

1.N>1，不大于N且和N互素的所有正整数的和是 1/2*N*eular(N)。推荐题目：HDOJ 3501 题解：点击打开链接

2.若(N%a==0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a;
3.若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);

4.对于素数n phi(n)=n-1

5.n==p^k phi(n)=(p-1)*p^(k-1)

6.若x,y互素 phi(x*y)=phi(x)*phi(y)

7.n=Σpi^ki phi(n)=n*Σ(1-1/pi)

8. a^(phi(p)-1) 是 a在modp下定义的逆元

9. 对于质数p 若n%p==0 phi(n*p)=phi(n)*p

10.对于质数p若n%p!=0 phi(n*p)=phi(n)*(p-1)

11.当n为奇数是 phi(2n)=phi(n)

12.φ(n)=∑d|nφ(d) (d|n)指n是d的倍数