完全理解欧拉函数的计算和欧拉定理（使用线性筛求解）（使用试除法求解）

【G09 筛法求欧拉函数】 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 被抠的键盘（构造题，我们需要思考的就是，我们有没有办法化繁为简？）（一般这种构造题目，无解情况不会特别多）

这个对的原因是，显然，和 $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 都是质数，因此倍数与倍数之间互不干扰）给筛掉。

当然，如果进行朴素相减，会出现问题。

不过，那为什么乘积不会出现这个问题呢？答案就是容斥原理。

这就是乘法的容斥原理。因为乘法的本质就是在枚举子集，只要一个负号，让其符合这个容斥原理的奇减偶加特性即可。

/*
 * 试除法求一个数的欧拉函数（也就是求 [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}$。