完全理解欧拉函数的计算和欧拉定理（使用线性筛求解）（使用试除法求解） · znzryb
【G09 筛法求欧拉函数】 [https://www.bilibili.com/video/BV1VP411p7Bs/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37](https://www.bilibili.com/video/BV1VP411p7Bs/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37)
[The 6th Liaoning Provincial Collegiate Programming Contest-2025-辽宁省赛-B. Be knocked off 被抠的键盘（构造题，我们需要思考的就是，我们有没有办法化繁为简？）（一般这种构造题目，无解情况不会特别多）](/2026/03/13/20260313-44a00cf0)
这个对的原因是，显然，和 $p^k$ 不互素的只有 p 的倍数，因此就是 $\phi(p^k)=p^k-(p 的倍数的数量)$。
$1 \cdot p,\quad 2 \cdot p,\quad 3 \cdot p,\quad 4 \cdot p,\quad 5 \cdot p,\quad 6 \cdot p,\quad \ldots,\quad (p^{k-1} - 2) \cdot p,\quad (p^{k-1} - 1) \cdot p,\quad p^{k-1} \cdot p$
p 的倍数的系数可以从 $1$ 一直取到 $p^{k-1}$，**所以一共** $p^{k-1}$ **个**。最后一项 $p^{k-1} \cdot p = p^k$，刚好是上界。
因此 $\phi(p^k)=p^k-p^{k-1}$。
有了上面的这个公式，就不难推出如下式子。
其实这个式子，形象化的理解，就是不断的把 n 里面，p 的倍数（p 都是质数，因此倍数与倍数之间互不干扰）给筛掉。
当然，如果进行朴素相减，会出现问题。
不过，那为什么乘积不会出现这个问题呢？答案就是容斥原理。
这就是乘法的容斥原理。因为乘法的本质就是在枚举子集，只要一个负号，让其符合这个容斥原理的奇减偶加特性即可。
```cpp
/*
* 试除法求一个数的欧拉函数（也就是求 [1,n] 内与其互素的数的个数）
* 2026-03-13: AC https://codeforces.com/gym/106380/submission/366492238
*/
long long euler_phi(long long n) {
long long res = n;
// p 从 2 开始，逐个递增，试到 sqrt(n) 为止
for (long long p = 2; p * p <= n; p++) {
// 如果 p 能整除 n，那么 p 一定是质数。
// 为什么？因为如果 p 是合数，比如 p = 6 = 2 × 3，
// 那么在 p=2 和 p=3 的时候，n 中的 2 和 3 已经被除干净了，
// 此时 n 不可能被 6 整除，所以 n % 6 != 0，这个 if 进不来。
// 因此能进到这个 if 里的 p，一定是质因子。
if (n % p == 0) {
// 发现质因子 p，对 res 乘上 (1 - 1/p) 这个因子
// 即 res = res / p * (p - 1)
res = res / p * (p - 1);
// 把 n 中所有的 p 除干净
// 这样后续更大的 p 的倍数就不可能再整除 n 了
while (n % p == 0) n /= p;
}
}
// 循环结束后，如果 n > 1，说明 n 还剩一个大于 sqrt(原始n) 的质因子
// （一个数最多只有一个大于 sqrt 的质因子）
if (n > 1) {
res = res / n * (n - 1);
}
return res;
}
```
那么都有上面的，非常符合直觉的计算公式了，我们也是非常 easy 的能够证明这个东西。
只要把这个东西全部列出来，就非常容易的可以证明。当然，要求 n，m 互素，否则他们的质数项一定会有交集，那么就失效了，积性函数性质。
这是 **Euler 定理**（欧拉定理）。
对于任意正整数 $m$ 和整数 $a$，若 $\gcd(a, m) = 1$，则
$$
a^{\varphi(m)} \equiv 1 \pmod{m}
$$
**证明**：考虑模 $m$ 的缩系（即 $1$ 到 $m$ 中所有与 $m$ 互素的数构成的集合 $S$，共 $\varphi(m)$ 个元素）。当 $\gcd(a, m) = 1$ 时，把 $S$ 中每个元素都乘以 $a$，得到的集合模 $m$ 后恰好还是 $S$（因为乘以 $a$ 是模 $m$ 缩系上的一个双射）。于是把所有元素的乘积写出来：
$$
\prod_{x \in S} (ax) \equiv \prod_{x \in S} x \pmod{m}
$$
左边提出 $a$：
$$
a^{\varphi(m)} \times \prod_{x \in S} x \equiv \prod_{x \in S} x \pmod{m}
$$
因为 $\prod_{x \in S} x$ **与** $m$ **互素**（**因为** $S$ **中每个元素都与** $m$ **互素**，这里我们用到了 S 的定义）（**说白了，只要是除数和 m 互素，就有逆元，就可以除**），可以两边消掉，就得到 $a^{\varphi(m)} \equiv 1 \pmod{m}$。
它的特殊情况是 **Fermat 小定理**：当 $m = p$ 为素数时，$\varphi(p) = p - 1$，即 $a^{p-1} \equiv 1 \pmod{p}$。