我的算法书 - 欧拉函数

搞懂欧拉函数：从定义到代码实现

欧拉函数（Euler’s Totient Function, $\varphi$ ）是数论中最重要的基石之一，也是算法竞赛（ACM/ICPC/OI）中的必考点。

在数论和算法竞赛中，我们经常会遇到一个神秘的符号： $\varphi(n)$ 。它不仅是 RSA 加密算法的核心，也是解决很多取模、循环节问题的关键。今天我们就来彻底搞懂欧拉函数及其C++ 代码实现。

1 什么是欧拉函数？

欧拉函数 $\varphi(n)$ 的定义非常简单：

对于正整数 $n$ ， $\varphi(n)$ 表示在小于等于 $n$ 的正整数中，与 $n$ 互质的数的个数。

注：互质（Coprime）的意思是两个数的最大公约数 $\gcd(a, b) = 1$ 。

举个栗子： 我们来看 $n = 6$ 。小于等于 6 的数有： $1, 2, 3, 4, 5, 6$ 。

$\gcd(1, 6) = 1$ （互质）✅
$\gcd(2, 6) = 2$ （不互质）
$\gcd(3, 6) = 3$ （不互质）
$\gcd(4, 6) = 2$ （不互质）
$\gcd(5, 6) = 1$ （互质）✅
$\gcd(6, 6) = 6$ （不互质）

与 6 互质的数只有 1 和 5，共 2 个。所以 $\varphi(6) = 2$ 。

2 核心计算公式（推导原理）

如果 $n$ 很小，我们可以枚举。但如果 $n$ 是 $10^9$ 级别呢？我们需要通项公式。

根据算术基本定理，任意正整数 $n$ 都可以唯一分解为素因子的乘积：

n = p_1^{k_1} \times p_2^{k_2} \times \dots \times p_m^{k_m}

欧拉函数的通项公式为：

\varphi(n) = n \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \times \dots \times \left(1 - \frac{1}{p_m}\right)

为什么是这个公式？

利用容斥原理可以通俗理解：

我们想求 $1$ 到 $n$ 中与 $n$ 互质的数。
初始假设所有数都互质，共 $n$ 个。
减去 $p_1$ 的倍数，剩下 $n(1 - \frac{1}{p_1})$ 。
再减去 $p_2$ 的倍数……以此类推。
注意：欧拉函数只和 $n$ 的质因子有关，和质因子的指数（次数）无关。

转换为代码逻辑

在计算机中，浮点数运算（ $1 - \frac{1}{p}$ ）不仅慢而且有精度误差。我们将公式变形一下，方便整数运算：

n \times \left(1 - \frac{1}{p}\right) = n \times \frac{p-1}{p} = \frac{n}{p} \times (p-1)

所以在代码中，对于每一个质因子 $p$ ，我们只需要执行：res = res / p * (p - 1)。

3 代码实现详解

这就是你手中那段代码的完整逻辑解析。这个算法的时间复杂度是 $O(\sqrt{n})$ ，非常高效。

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

        typedef long long ll;

// 试除法求欧拉函数
// 输入 n，返回 phi(n)
ll get_phi(ll n) {
    ll res = n; // 初始化结果为 n，对应公式中的 n
    
    // 1. 遍历寻找质因子
    // 我们只需要遍历到 sqrt(n) 即可，这和判断素数的逻辑一样
    for (ll i = 2; i * i <= n; ++i) {
        
        // 2. 如果 i 能整除 n，说明 i 是 n 的一个质因子
        if (n % i == 0) {
            
            // 3. 应用公式：res = res * (1 - 1/i)
            // 变形为整数运算：res = res / i * (i - 1)
            res = res / i * (i - 1);
            
            // 4. 【关键】除尽当前的质因子 i
            // 欧拉函数只跟“有哪些质因子”有关，跟因子的个数无关
            // 例如 12 = 2^2 * 3，我们处理 2 的时候，要把 12 里的两个 2 都除掉，变成 3
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    
    // 5. 处理剩余的那个大质因子
    // 如果循环结束后 n > 1，说明 n 本身还剩下一个大于 sqrt(原n) 的质因子
    // 例如 n = 14 (2 * 7)，循环处理了 2，剩下 7，7 > sqrt(14)，需要再处理一次
    if (n > 1) {
        res = res / n * (n - 1);
    }
    
    return res;
}

4 关键点 Q&A

Q1: 为什么循环只到 $\sqrt{n}$ ？ A: 因为一个合数 $n$ 最多只有一个大于 $\sqrt{n}$ 的质因子。我们在循环中处理掉了所有小于等于 $\sqrt{n}$ 的质因子，最后剩下的 $n$ 如果大于 1，那它一定就是那个“最大的质因子”。

Q2: while (n % i == 0) n /= i; 这行代码有什么用？ A: 这是为了保证 $i$ 必定是质数。当我们从小到大枚举 $i$ 时：

当 $i=2$ 时，我们除掉了 $n$ 中所有的因子 2。
当枚举到 $i=4$ 时，由于 $n$ 已经不包含因子 2 了，所以 $n$ 绝不可能被 4 整除。
因此，if (n % i == 0) 成立时， $i$ 一定是质数。这也避免了我们重复计算同一个质因子。

Q3: 复杂度是多少？ A: 时间复杂度是 $O(\sqrt{n})$ 。对于 $10^9$ 范围内的数据，计算一次几乎是瞬间完成。

5 总结

求单个数字欧拉函数的步骤：

初始化答案 res = n。
从 $2$ 到 $\sqrt{n}$ 枚举质因子 $p$ 。
如果 $p$ 是因子：
- 更新答案：res = res / p * (p - 1)。
- 将 $n$ 中所有的 $p$ 除干净。
如果最后 $n > 1$ ，说明还有一个大质因子，再更新一次答案。

练习题目

luogu-P2303 [SDOI2012] Longge 的问题 tags: [数论,欧拉函数]

下一步建议

这篇博客涵盖了求单个数字欧拉函数的方法。如果你在做算法题时，需要求 $1$ 到 $N$ 之间所有数的欧拉函数（例如 $N=10^6$ ），使用这个方法会超时（总复杂度 $O(N\sqrt{N})$ ）。

这种情况下，你需要学习线性筛（欧拉筛）求欧拉函数，它可以在 $O(N)$ 的时间内求出所有解。你想学习线性筛的相关代码吗？

目录