在数论中，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目
用φ(n) 来表示欧拉函数，特别的是对于一个数n，1也是与n互质的，则 φ(1) = 1；
欧拉函数的通式：$phi left( n ight) =ncdot left( 1-dfrac {1}{p_{1}} ight) .left( dfrac {1}{1-p_{2}} ight) cdot ldots cdot left( 1-dfrac {1}{p_{k}} ight)$
对于公式的推导，只有感叹一句：欧拉牛逼！
这里主要讲一下怎么转化为代码。首先要知道的是 p1，p2，... pk 都是 n 的质因数(不重复）
例如 12 = 2 * 2 * 3，那么 p1 = 2， p2 = 3；
则：φ(12) = 12 * (1 - 1/2) * (1 - 1/3) = 4；这四个数分别是 1，5，7，11
接下来考虑怎么求 φ(n)，由于φ(n) = n * (1 - 1/p1) * (1 - 1/p2) .....
我们设 ans = n，展开 n * (1 - 1/p1) = ans * (1 - 1/p1) = ans - ans/p1，-->> ans = ans - ans/p1 由此类推我们可以得到递推公式：
ans = ans - ans/pi （pi 是 n 的质因数）
接下来上代码：
这只是对于求一个数的欧拉函数。复杂度是 $Oleft( log n ight)$ 的。
那么如果我们要求的是 $left[ 1,n ight]$ 区间的欧拉函数的话，就需要更快的方法了。
我这里介绍的是根据 欧拉筛来求欧拉函数，是线性的。如果对欧拉筛不懂的话，可以先去学习一波，不然不容易理解代码
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 using namespace std; 5 const int N = 1e5 + 10; 6 7 int phi[N], mark[N], prime[N]; 8 //phi 用来记录欧拉函数，mark来标记素数， prime来存素数 9 int lenPrime = 0; 10 11 void euler() 12 { 13 //1 要特判 14 phi[1] = 1; 15 memset(mark, 0, sizeof(mark)); 16 for(int i = 2; i < N; i++) 17 { 18 //如果 i 是素数 19 if(mark[i] == 0) 20 { 21 phi[i] = i - 1; //素数的欧拉函数就是 自己 - 1 22 prime[lenPrime++] = i; //把素数记录下来 23 } 24 //循环条件 ： j 就是遍历prime数组，i * prime[j] < N 也是显然易见的 25 for(int j = 0; j < lenPrime && i * prime[j] < N; j++) 26 { 27 // i* prime[j] 是合数，所以标记为 1 28 mark[i * prime[j]] = 1; 29 if(i % prime[j] == 0) 30 { 31 phi[i*prime[j]] = prime[j] * phi[i]; 32 break; 33 } 34 else phi[i * prime[j]] = phi[i] * phi[prime[j]]; 35 } 36 } 37 } 38 39 int main() 40 { 41 euler(); 42 for(int i = 1; i <= 20; i++) printf("E[%d] = %d ", i, phi[i]); 43 return 0; 44 }
这里主要对两个地方进行讲解：
第一是 31行的：
if(i % prime[j] == 0) phi[i*prime[j]] = prime[j] * phi[i];
我们设 a = i * prime[j] ；显然 prime[j] 是 a 的一个质因子
1.那么 a 的 其他质因子 显然 在 i 里，也就是说 a 的质因子 = i 的质因子 + prime[j]
2.但由于 i % prime[j] == 0 ------> prime[j] 也是 i 的 质因子
综合 1 和 2 的结论 我们可以得出 a 的 质因子 = i 的质因子
例如 当 i = 6，prime[j] = 2 时，i* prime[j] = 12； 显然 6 % 2 == 0 ，则 6 的质因子都是 12 的质因子。
由欧拉函数 φ(i * prime[j]) = （prime[j] * i）* （1 - 1/p1) * (1 - 1/p2)....
= prime[j] * i * (1 - 1/p1) * (1 - 1/p2)...... //由于 p1，p2，....都是 i 的 质因子
= prime[j] * φ(i )
第二是 34 行的：
这里我们需要知道 积性函数 ： f(a*b) = f(a) * f(b) （a，b互质) 那么 f 这个函数就是一个积性函数
欧拉函数也是一个积性函数 所以当 a，b 互质时 ：φ(a * b) = φ(a) * φ(b)
关于欧拉函数暂时就讲到这里.............