欧拉函数
欧拉函数 \(\varphi(n)\) 表示 \(1 \sim n - 1\) 中与 \(n\) 互质的数的个数。显然的，当 \(n\) 为质数，有 \(\varphi(n) = n - 1\)。
性质与推导
-
显然的，当 \(\gcd(a,b)\)，有 \(\varphi(a \times b) = \varphi(a) \times \varphi(b)\)，oi-wiki 上管这个叫做积性函数。
-
显然的，当 \(b \bmod a = 0\)，有 \(\varphi(a \times b) = a \times \varphi(b)\)。
-
设 \(n = \prod\limits_{i = 1}^{s} p_i^{c_i}\)，即将 \(n\) 进行唯一分解，有 \(\varphi(n) = n \times \prod\limits_{i = 1}^{s}\frac{p_i - 1}{p_i}\)，证明如下：
\(\varphi(p^c) = p^c - p^{c - 1} = p^{c - 1} \times (p - 1)\)，显然，值不超过 \(p\) 的自然数中，有 \(p^{c - 1}\) 个 \(p\) 的倍数，故可得上式；
由欧拉函数的积性，当 \(\gcd(a,b)\)，有 \(\varphi(a \times b) = \varphi(a) \times \varphi(b)\)，所以
\[\begin{aligned} \varphi(n) &= \prod\limits_{i = 1}^{s}\varphi(p_i^{c_i})\\ &= \prod\limits_{i = 1}^{s}p_i^{c_i - 1} \times (p_i - 1)\\ &= \prod\limits_{i = 1}^{s}p_i^{c_i} \times \frac{p_i - 1}{p_i}\\ &= n \times \prod\limits_{i = 1}^{s}\frac{p_i - 1}{p_i} \end{aligned} \]根据最后一条我们能够筛出 \(\varphi(n)\)。
$\tt{Link}$
il int get_phi(int x) {
int phi = x;
for (int i = 2; i * i <= x; ++ i ) {
if (x % i == 0) {
phi = phi / i * (i - 1);
while (x % i == 0) x /= i;
}
}
if (x > 1) phi = phi / x * (x - 1);
return phi;
}