欧拉定理

欧拉函数

1到n中与n互质的数字的个数

用n的分解质因数的结果计算欧拉函数

$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$

$\varphi(n) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})\cdots(1 - \frac{1}{p_k})$

欧拉函数是积性函数，可以结合筛法在 $O(n)$ 的时间预处理 $1$ 到 $n$ 的欧拉函数值

如果a和p互质
$a^{\varphi(p)} \bmod p = 1$

如果不互质，需要用扩展欧拉定理

P5091 【模板】扩展欧拉定理

如果 $x$ 和 $p$ 互质
$x^{\varphi(p)} \bmod p = 1$
$x^n \bmod p = x^{n \bmod \varphi(p)} \bmod p$

如果 $x$ 和 $p$ 不互质，并且 $n \geq \varphi(p)$
$x^n \bmod p == x^{n \bmod \varphi(p) + \varphi(p)} \bmod p$