欧拉函数

欧拉函数的性质：

1) p^k型欧拉函数:

若N是质数p(即N=p), φ(n)= φ(p)=p-p^(k-1)=p-1。

若N是质数p的k次幂(即N=p^k)，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)。

(2)mn型欧拉函数

设n为正整数，以φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值。若m,n互质，φ(mn)=φ(m)φ(n)。

(3)特殊性质:

若n为奇数时，φ(2n)=φ(n)。

对于任何两个互质的正整数a,n(n>2)有:a^φ(n)=1 mod n (恒等于)此公式即 欧拉定理

当n=p 且 a与素数p互质(即:gcd(a,p)=1)则上式有: a^(p-1)=1 mod n (恒等于)此公式即 费马小定理

(4)对于n，p为n的素因子

φ(p*n) = p*φ(n)(由最根本的定理可知)

欧拉函数模板

 1 int euler_phi(int n)//求单个
 2 {
 3     int m = (int)sqrt(n + 0.5);
 4     int ans = n;
 5     for(int i = 2; i <= m; i++)if(n % i == 0)
 6     {
 7         ans = ans / i * (i - 1);
 8         while(n % i == 0)n /= i;
 9     }
10     if(n > 1)ans = ans / n * (n - 1);
11     return ans;
12 }
13 void phi_table(int n, int* phi)//打表
14 {
15     for(int i = 0; i <= n; i++)phi[i] = i;
16     for(int i = 2; i <= n; i++)if(phi[i] == i)
17         for(int j = i; j <= n; j += i)phi[j] = phi[j] / i * (i - 1);
18 }

 1 void phi_table(int n)//稍微快一点的打表 

 2 {
 3     phi[1] = 1;
 4     for(int i = 2; i <= n; i++)
 5     {
 6         if(!phi[i])//素数
 7         {
 8             for(int j = i; j <= n; j += i)
 9             {
10                 if(!phi[j])phi[j] = j;
11                 phi[j] = phi[j] / i * (i - 1);
12             }
13         }
14     }
15 }

 1 ll phi[maxn];
 2 ll prime[maxn];
 3 bool not_prime[maxn];
 4 int cnt;
 5 void phi_table(int n)//最快打表 O(n)
 6 {
 7     phi[1] = 1;
 8     for(int i = 2; i <= n; i++)
 9     {
10         if(!not_prime[i])//素数
11         {
12             prime[++cnt] = i;
13             phi[i] = i - 1;
14         }
15         for(int j = 1; j <= cnt && i * prime[j] <= n; j++)
16         {
17             not_prime[i * prime[j]] = 1;
18             if(i % prime[j] == 0)//第j个素数是i的因子
19             {
20                 phi[i * prime[j]] = phi[i] * prime[j];
21                 break;
22             }
23             else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
24         }
25     }
26 }