介绍
欧拉函数是小于 \(x\) 的整数中与 \(x\) 互质的数的个数，一般用 \(\varphi(x)\) 表示。特殊的， \(\varphi(1)=1\) 。
内容
通式：\(\varphi(x)=x\prod_{i=1}^n{1-\frac{1}{p_i}}\)
其中， \(p_1,p_2...p_n\) 为 \(x\) 的所有质因数， \(x\in N^*\) 。
性质
- 对于质数 \(p\) , \(\varphi(p)=p-1\) 。
- 若 \(p\) 为质数，\(n=p^k\) ，则 \(\varphi(n)=p^k-p^{k-1}\) 。
- 欧拉函数是积性函数，但不是完全积性函数。若 \(m,n\) 互质，则 \(\varphi(m*n)=\varphi(m)*\varphi(n)\) 。特殊的，当 \(m=2,n\) 为奇数时， \(\varphi(2*n)=\varphi(n)\) 。
- 当 \(n>2\) 时， \(\varphi(n)\) 是偶数。
- 小于 \(n\) 的数中，与 \(n\) 互质的数的总和为 \(\varphi(n)*n/2 \ \ \ (n>1)\) 。
- \(n=\sum_{d|n}\varphi(d)\) ，即 \(n\) 的因数(包括１和它本身)的欧拉函数之和为 \(n\) 。
容斥原理求欧拉函数
-
将 \(N\) 分解为不同素数的乘积，即：
\[N=p_1^{r_1}*p_2^{r_2}*p_3^{r_3}*...*p_k^{r_k}\]
设 \(1\) 至 \(N\) 的 \(N\) 个数中为 \(p_i\) 倍数的集合为 \(A_i\) ，则有 \(|A_i|=\lfloor\frac{N}{p_i}\rfloor\) \((i=1,2,3,..,k)\)。
对于 \(p_i\not=p_j\) ， \(A_i\cap A_j\) 既是 \(p_i\) 的倍数也是 \(p_j\) 的倍数，即可得 \(|A_i\cap A_j|=\lfloor\frac{N}{p_ip_j}\rfloor\) \((1\le i,j \le k,i\not=j)\) 。
\[\begin{split} \varphi(N) &=|A_1\cap A_2 \cap A_3 \cap ... \cap A_k|\\ &=N-(\frac{N}{p_1}+\frac{N}{p_2}+...+\frac{N}{p_k})+(\frac{N}{p_1p_2}+\frac{N}{p_2p_3}+...+N)...\pm(\frac{N}{p_1p_2...p_k})\\ &=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k}) \end{split}\]
算法实现
时间复杂度：\(O(\sqrt{n})\)
int euler_phi(int n) {
int res = n;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
res = res / i * (i - 1);
while (n % i == 0) n /= i;
}
}
if (n != 1) res = res / n * (n - 1);
return res;
}