定义
欧拉函数 \(\phi(n)\) 代表的是 \([1,n]\) 之间与 \(n\) 互质的数量。
公式
\(\phi(n) = n \times (1- \frac{1}{p_1})\times (1- \frac{1}{p_2})\times (1- \frac{1}{p_3}) \times …… \times (1- \frac{1}{p_k})\)
其中：\(n\) 有 \(k\) 个质因数，而 \(p_i\) 就是其中的一个质因数。
推导
如何推导
推导的方式要用到容斥原理。
欧拉函数 \(\phi(n)\) 代表的是 \([1,n]\) 之间与 \(n\) 互质的数量，但是我们发现比较难想，于是正难则反，直接从不互质来入手，然后减掉就得出结果了。
如果 \(i\) 是不互质，那么 \(i\) 和 \(n\) 必将有共同的质因数。所以，我们可以通过 \(n\) 的每一个质因数进行倍数处理，然后容斥算出有多少是不互质的，因此也就可得出答案了。
推导过程
我们设：\(n\) 的质因数是：{ \(p_1,p_2,……,p_k\) }。
那么 \(p_i\) 在 \([1,n]\) 这个区间中的倍数就有 \(\frac{n}{p_i}\)。
为了方便推导，我们暂且先设 \(k=3\)。
于是就可以得到公式：
- \(n-\frac{n}{p_1}-\frac{n}{p_2}-\frac{n}{p_3}+\frac{n}{p_1 \times p_2}+\frac{n}{p_1 \times p_3} + \frac{n}{p_2 \times p_3} -\frac{n}{p_1 \times p_2 \times p_3}\)
在进行通分之后，我们发现这个式子其实已经等于 \(\phi(n)\) 了。
得证。
代码
定义法
-
只能处理一个数的 \(\phi\)。
-
思路是一边分解质因数一遍处理欧拉函数
int get_euler(int n) { int euler = n; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { euler = euler / i * (i - 1) //euler = euler * (1 - 1 / i); while (n % i == 0) n /= i; } } if (n > 1) euler = euler / n * (n - 1); return euler; }
线性筛法
-
在进行筛法的时候处理欧拉函数
-
可以在一次线性筛中处理出 \([1,n]\) 中的欧拉函数
int primes[N], cnt = 0; int euler[N]; bool st[N]; int get_euler(int n) { euler[1] = 1; // 1的欧拉函数值是1 // 线性筛模板 + 过程中求欧拉函数 for (int i = 2; i <= n; i++) { if (!st[i]) { primes[cnt ++] = i; euler[i] = i - 1; // (1)式 } for (int j = 0; primes[j] <= n / i; j++) { st[i *primes[j]] = true; if (i % primes[j] == 0) { euler[i * primes[j]] = euler[i] * primes[j]; //(2)式 break; } euler[i * primes[j]] = euler[i] * (primes[j] - 1);//(3)式 } } // 最后，euler数组中存的就是 1 ~ n 每个数的欧拉函数值 } urn euler; }
一些等式
-
当 \(n\) 是质数的时候，\(\phi(n) = n-1\)。
-
当 \(n\) 是质数的时候，存在 \(n^k\) 使得 \(\phi(n^k) = (n-1) \times n ^{k-1}\)
-
积性函数，如果 \(n\) 与 \(m\) 互质，则 \(\phi(n×m)=\phi(n)×\phi(m)\)
参考文献：