学习笔记：求解欧拉函数
chenxi797
·
·
算法·理论
什么是欧拉函数？
$$
\varphi(n) = | \{ 1 \le k \le n | \gcd(k,n) = 1 \} |
$$
## 如何求解？
#### 1.若 $n$ 为质数：
$$
\varphi(n) = n - 1
$$
#### 2.若 $n = p^k$，$p$为质数：
$$
\varphi(p^k) = p^k - p^{k - 1} = p^k \left( 1 - \frac{1}{p} \right)
$$
#### 3.若 $n = a \times b,\gcd(a,b) = 1$：
$$
\varphi(ab) = \varphi(a)\varphi(b)
$$
#### 4.通项公式：
对于任意正整数 $n$，其质因数分解为：
$$
n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}
$$
则：
$$
\varphi(n) = n \times \left(1 - \frac{1}{p_1} \right) \times \left(1 - \frac{1}{p_2} \right) \times \cdots \times \left(1 - \frac{1}{p_m} \right) = n \prod_{i = 1}^m \left(1 - \frac{1}{p_i} \right)
$$
## 关于代码实现
我们注意到通项公式中有一个分数：$\frac{1}{p_i}$。在数论中，我们需要让所有数尽可能为整数。而在 $\texttt{C++}$ 环境中，$\frac{1}{p_i}$ 这个分数在整数下一定为 $0$。
所以，我们需要改造这个式子。换句话说，我们需要避免精度问题。
我们先将通项公式转化成伪代码语言：
```
res <- n
for i = 2 to sqrt n:
if (i 为质数且 i|n)
res <- res * (1 - 1 / i);
```
重点就在这个式子：
$$
res \gets res * (1 - 1 \ / \ i)
$$
去括号，得：
$$
res \gets res - res \ / \ i
$$
将 $res \ / \ i$ 提出来，得
$$
res \gets res \ / \ i \times (i - 1)
$$
这个式子不会出现精度问题。
为什么 $res \ / \ i$ 不会出现精度问题呢？
因为 $i$ 是 $n$ 的质因子，那么必然有 $i \mid res$。
这样代码就好写了。