1. 从一道面试题说起：为什么需要“欧拉函数模板”？

最近在帮朋友准备算法面试，他给我看了一道高频的题目，大意是：给定一个正整数 n ，要求计算 1 到 n 之间有多少个数与 n 互质。他吭哧吭哧写了个循环，对每个数都去求一次最大公约数 gcd(i, n) ，如果等于 1 就计数。当 n 比较小的时候，比如 n=10 ，这方法没问题。但题目给的 n 范围是 1 <= n <= 10^9 ，甚至更大。他那个 O(n log n) 的算法直接超时，当场就懵了。

我告诉他，这道题考的核心根本不是暴力枚举，而是一个数论里的经典工具—— 欧拉函数 。欧拉函数 φ(n) 的定义，就是小于等于 n 的正整数中，与 n 互质的数的个数。题目问的，其实就是 φ(n) 的值。而计算 φ(n) ，如果直接用定义去数，和暴力没区别。真正高效的方法，是利用欧拉函数的几个核心性质和计算公式，将时间复杂度降到 O(√n) 。在实际的算法竞赛、密码学应用，或者处理大数相关的业务逻辑时，一个高效、鲁棒的欧拉函数实现，就像一把瑞士军刀，必不可少。今天，我们就来彻底拆解这个“欧拉函数模板”，不仅给你代码，更要讲清楚背后的数学原理、不同场景下的实现变体，以及那些容易踩进去的坑。

2. 欧拉函数的数学基石：从定义到计算公式

要写出好用的模板，不能只当“调包侠”，得先明白它到底在算什么。欧拉函数 φ(n) ，也叫 Euler‘s totient function 。它的定义很直观： φ(n) = #{k: 1 ≤ k ≤ n, gcd(k, n) = 1} 。比如 φ(8) = 4 ，因为 1, 3, 5, 7 这四个数与 8 互质。

但定义无法用于高效计算。欧拉函数的威力，源于它的三个核心性质：

性质一：积性函数。 如果两个正整数 a 和 b 互质（即 gcd(a, b) = 1 ），那么 φ(a*b) = φ(a) * φ(b) 。这个性质允许我们将一个大数 n 分解成多个互质的因子，分别计算后再相乘，极大地简化了问题。

性质二：质数的欧拉函数。 如果 p 是一个质数，那么 φ(p) = p - 1 。这很好理解，因为对于一个质数 p ，从 1 到 p-1 的所有数都与它互质。

性质三：质数幂的欧拉函数。 如果 p 是质数， k 是正整数，那么 φ(p^k) = p^k - p^(k-1) = p^(k-1) * (p - 1) 。这是因为在 1 到 p^k 这些数中，只有那些包含因子 p 的数才不与 p^k 互质，这样的数有 p^(k-1) 个（即 p, 2p, 3p, ..., p^k ），所以互质的数就是总数减去这些。

基于这三个性质，我们可以推导出欧拉函数的通用计算公式。任何一个大于 1 的正整数 n ，都可以进行质因数分解： n = p1^k1 * p2^k2 * ... * pm^km ，其中 pi 是质数， ki 是正整数。由于不同的质数幂之间是互质的，根据积性函数性质：

φ(n) = φ(p1^k1) * φ(p2^k2) * ... * φ(pm^km)

再根据质数幂的性质，将每个 φ(pi^ki) 替换为 pi^(ki-1) * (pi - 1) ：

φ(n) = [p1^(k1-1) * (p1 - 1)] * [p2^(k2-1) * (p2 - 1)] * ... * [pm^(km-1) * (pm - 1)]

这个式子可以进一步整理成更紧凑的形式。把每个 pi^(ki-1) 和前面的 pi 合并考虑，可以得到最常用的计算公式：

φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pm)

这个公式是模板代码的灵魂。 它告诉我们，计算 φ(n) 的核心步骤，其实就是对 n 进行质因数分解，找出所有不同的质因子 p ，然后套用这个连乘公式。

注意：这里有一个非常关键的细节，公式中 (1 - 1/pi) 是针对 不同的质因子 。比如 n=12=2^2*3 ，我们只乘 (1-1/2) 和 (1-1/3) ，而不是乘两次 (1-1/2) 。在代码实现时，我们通常会在分解质因数的过程中，每找到一个质因子 p ，就让 n 不断除以 p 直到不能再除（这样就去掉了该质因子的所有幂次），然后给结果乘上 (p-1) 。但等一下，这里又涉及到一个更高效的写法，我们会在后面的模板部分详细解释。

3. 单次求值模板： O(√n) 的经典实现

理解了公式，我们就可以动手写代码了。最常用、也是最基础的场景是： 给定一个 n ，求 φ(n) 。 下面给出这个场景下的标准模板，并逐行解析。

// 函数功能：计算欧拉函数 φ(n)
// 时间复杂度：O(√n)
long long euler_phi(long long n) {
    long long ans = n; // 初始化为 n，对应公式中的 n
    long long temp = n; // 用一个临时变量操作 n，避免修改原值
    // 遍历所有可能的小于等于 √temp 的因子
    for (long long p = 2; p * p <= temp; p++) {
        // 如果 p 是 temp 的因子，那么 p 一定是质数
        if (temp % p == 0) {
            // 找到了一个质因子 p，根据公式 ans = ans / p * (p-1)
            // 这里先除后乘是为了防止中间结果溢出，但更常见的写法是下面这种：
            ans = ans / p * (p - 1);
            // 将 temp 中所有的因子 p 除尽
            while (temp % p == 0) {
                temp /= p;
            }
        }
    }
    // 循环结束后，temp 可能大于 1。此时 temp 一定是大于 √n 的质因子（且仅有一个）
    // 例如 n=13，循环不会进入，temp=13，它是一个质数，需要处理
    if (temp > 1) {
        ans = ans / temp * (temp - 1);
    }
    return ans;
}

代码逻辑深度解析：

1. 初始化 ： ans = n ，对应公式 φ(n) = n * Π(1 - 1/p) 中的初始 n 。
2. 质因数分解循环 ： for (long long p = 2; p * p <= temp; p++) 这是标准的试除法分解质因数。为什么循环条件是 p * p <= temp ？因为一个合数 temp 至少有一个不大于其平方根的质因子。我们不断用找到的因子去除 temp ，所以 temp 会越来越小。当 temp 被除到小于 p*p 时，它要么是 1 ，要么是一个大于当前 p 的质数。
3. 找到质因子后的操作 ：
   • if (temp % p == 0) ：当 p 能整除当前的 temp 时， p 一定是 temp 的一个质因子。为什么？因为我们的循环是从 2 开始的，并且内层 while 循环会把 temp 中所有 p 的因子都除掉。所以当再次遇到 temp % p == 0 时，这个 p 不可能是之前某个质因子的倍数（否则早被除掉了），它自己就是一个新的质因子。
   • ans = ans / p * (p - 1); ：这行代码是公式 ans *= (1 - 1/p) 的等价变形。 ans / p * (p-1) 等于 ans * (p-1)/p ，也就是 ans * (1 - 1/p) 。先除后乘可以在一定程度上避免整数溢出，但前提是 ans 能被 p 整除（这由数学性质保证，因为 p 是 n 的因子，而 ans 初始为 n ，且在计算过程中始终是 n 乘以若干个分数，结构上依然保持 n 的因子关系）。
   • while (temp % p == 0) temp /= p; ：这步至关重要！它去掉了 temp 中所有 p 的幂次。这保证了我们找到的每个 p 都是 不同的质因子 ，并且后续的循环不会再处理这个 p 的倍数。这正是实现公式中“对不同质因子连乘”的关键。
4. 处理剩余的大质因子 ：循环结束后，如果 temp > 1 ，那么此时的 temp 一定是 n 的一个质因子，并且它大于原始的 √n 。因为如果它是合数，它必然包含一个小于等于其平方根的因子，而这个因子也必然小于等于原始的 √n ，应该在之前的循环中被找到并除尽了。所以，它一定是一个质数。我们需要对它进行同样的操作： ans = ans / temp * (temp - 1); 。

时间复杂度分析 ：主要的开销在于 for 循环，循环次数最多为 √n 级别（尽管 temp 在减小，但最坏情况下， n 本身是个大质数，我们需要遍历 2 到 √n 的所有数才能确认）。因此，单次计算 φ(n) 的时间复杂度是 O(√n) 。对于 n <= 10^12 的情况，这个复杂度通常是可接受的。

4. 区间预处理模板：埃氏筛与欧拉筛的妙用

单次求值 O(√n) 很快，但如果题目需要频繁查询，比如求 φ(1) 到 φ(N) 的所有值，或者需要多次计算不同 n 的欧拉函数，每次都去分解质因数就不划算了。这时，我们需要 预处理 出一定范围内所有数的欧拉函数值。这通常借助筛法来完成，主要有两种思路： 埃拉托斯特尼筛法（埃氏筛） 和 线性筛（欧拉筛） 。

4.1 基于埃氏筛的 O(N log log N) 预处理

埃氏筛的思想可以巧妙地用来计算欧拉函数。我们初始化一个数组 phi[] ，令 phi[i] = i 。然后，我们模仿找质数的过程，遍历所有数。

// 函数功能：用埃氏筛法预处理 [1, N] 的欧拉函数
// 时间复杂度：O(N log log N)，空间复杂度：O(N)
const int MAXN = 1000000; // 预处理范围
long long phi[MAXN + 5];

void euler_phi_sieve_eratosthenes(int N) {
    // 初始化
    for (int i = 1; i <= N; i++) {
        phi[i] = i;
    }
    // 遍历所有数
    for (int i = 2; i <= N; i++) {
        // 如果 phi[i] == i，说明 i 是质数（因为只有质数在初始化后还没被更新过）
        if (phi[i] == i) {
            // 对于质数 i，其欧拉函数值为 i-1
            // phi[i] = i - 1; // 这一步可以合并到下面的循环中
            // 遍历所有 i 的倍数 j
            for (int j = i; j <= N; j += i) {
                // 根据公式 φ(n) = n * Π(1 - 1/p)，对于 j 来说，i 是它的一个质因子
                // 所以 phi[j] 需要先除以 i，再乘以 (i-1)
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }
}

原理与注意事项：

• 外层循环 i 从 2 到 N 。
• 当 phi[i] == i 时，意味着 i 还没有被任何比它小的质数筛过，因此 i 一定是质数。
• 对于一个质数 i ，我们遍历它的所有倍数 j 。对于每个 j ， i 都是它的一个质因子。根据欧拉函数公式 φ(n) = n * Π(1 - 1/p) ，我们需要对 phi[j] （初始值为 j ）乘上 (1 - 1/i) ，即 phi[j] = phi[j] * (i-1) / i 。代码中写成先除后乘 phi[j] / i * (i-1) 是等价的，并且能保证整除。
• 这个算法为什么正确？因为每个合数 j 都会被它的每一个质因子 i 处理一次，并且处理的顺序无关紧要（乘法满足交换律）。最终 phi[j] 就变成了 j * Π(1 - 1/p) ，正是欧拉函数的值。
• 复杂度 ：这个算法的时间复杂度与埃氏筛类似，为 O(N log log N) ，对于 N 在 10^7 量级时非常高效。 但有一个小坑 ：在 j 循环中，我们是从 j = i 开始的，这包括了 i 本身。对于质数 i ， phi[i] 会在这次循环中被更新为 i / i * (i-1) = i-1 。所以前面代码中注释掉的 phi[i] = i-1 其实是不需要的。

4.2 基于线性筛（欧拉筛）的 O(N) 预处理

埃氏筛已经很快，但线性筛能做到真正的 O(N) ，并且在某些内存访问模式上更优。线性筛的核心是保证每个合数只被它的最小质因子筛掉一次。利用这个性质，我们可以在筛的同时递推求出欧拉函数。

// 函数功能：用线性筛法预处理 [1, N] 的欧拉函数，同时得到质数表
// 时间复杂度：O(N)，空间复杂度：O(N)
const int MAXN = 1000000;
int phi[MAXN + 5];       // 欧拉函数值
int primes[MAXN + 5];    // 质数表
bool is_prime[MAXN + 5]; // 标记是否为质数，初始全为 true
int cnt = 0;             // 质数个数

void euler_phi_sieve_linear(int N) {
    // 初始化
    for (int i = 2; i <= N; i++) {
        is_prime[i] = true;
    }
    phi[1] = 1; // 定义 φ(1) = 1
    // 线性筛主体
    for (int i = 2; i <= N; i++) {
        if (is_prime[i]) {
            primes[cnt++] = i;          // i 是质数，加入质数表
            phi[i] = i - 1;             // 质数的欧拉函数值
        }
        // 遍历当前已知的所有质数
        for (int j = 0; j < cnt; j++) {
            long long next = (long long)i * primes[j];
            if (next > N) break;        // 超过范围，跳出
            is_prime[next] = false;     // 用最小质因子 primes[j] 筛掉合数 next
            // *** 核心：根据 i 和 primes[j] 的关系递推 phi[next] ***
            if (i % primes[j] == 0) {
                // 情况一：primes[j] 是 i 的质因子
                // 那么 primes[j] 也是 next 的质因子，且不是新的质因子
                // 公式：φ(next) = φ(i) * primes[j]
                phi[next] = phi[i] * primes[j];
                break; // 保证每个合数只被最小质因子筛一次
            } else {
                // 情况二：primes[j] 不是 i 的质因子
                // 那么 primes[j] 是 next 的最小质因子，且与 i 互质
                // 根据积性函数性质：φ(next) = φ(i) * φ(primes[j]) = φ(i) * (primes[j] - 1)
                phi[next] = phi[i] * (primes[j] - 1);
            }
        }
    }
}

递推原理的详细证明（这是理解模板的关键）：

线性筛在标记合数 next = i * primes[j] 时， primes[j] 一定是 next 的 最小质因子 。我们根据 i 是否包含 primes[j] 这个因子，分两种情况推导 φ(next) ：

1. i % primes[j] == 0 ：这意味着 primes[j] 是 i 的一个质因子。设 i = primes[j]^k * m ，其中 m 与 primes[j] 互质。那么 next = i * primes[j] = primes[j]^(k+1) * m 。

   • 计算 φ(i) ： φ(i) = φ(primes[j]^k) * φ(m) = [primes[j]^(k-1) * (primes[j]-1)] * φ(m) 。
   • 计算 φ(next) ： φ(next) = φ(primes[j]^(k+1)) * φ(m) = [primes[j]^k * (primes[j]-1)] * φ(m) 。
   • 对比两者： φ(next) = φ(i) * primes[j] 。
   • 直观理解 ： next 相比 i ，只是多乘了一个已有的质因子 primes[j] ，并没有引入新的质因子。根据公式 φ(n)=n*Π(1-1/p) ， next 的质因子集合与 i 相同，所以 φ(next)/next = φ(i)/i 。又因为 next = i * primes[j] ，所以 φ(next) = (φ(i)/i) * next = φ(i) * primes[j] 。

2. i % primes[j] != 0 ：这意味着 primes[j] 不是 i 的因子。由于 primes[j] 是质数，所以 gcd(i, primes[j]) = 1 ，即 i 与 primes[j] 互质。

   • 根据欧拉函数的积性性质，对于互质的两个数 a 和 b ，有 φ(a*b) = φ(a) * φ(b) 。
   • 所以 φ(next) = φ(i * primes[j]) = φ(i) * φ(primes[j]) = φ(i) * (primes[j] - 1) 。

break 的作用 ：在线性筛中，当 i % primes[j] == 0 时，必须 break 。这是因为此时 primes[j] 已经是 i 的最小质因子。对于下一个更大的质数 primes[j+1] ， next' = i * primes[j+1] 的最小质因子应该是 primes[j] 而不是 primes[j+1] （因为 i 包含了 primes[j] ）。如果继续循环，就会用非最小质因子去筛数，破坏了“每个合数只被最小质因子筛一次”的规则，可能导致 phi[] 被错误计算多次。

提示：线性筛求欧拉函数的模板非常经典且高效，建议理解并记忆。在需要一次性处理大量欧拉函数查询，或者需要同时用到质数表和欧拉函数值的题目中（比如某些莫比乌斯反演、狄利克雷卷积的题目），这个模板是首选。

5. 模板的变体、边界与实战踩坑点

掌握了基础的单点求值和区间预处理模板，我们还需要了解一些常见的变体和必须注意的边界条件，这些都是实战中容易出错的地方。

5.1 需要返回质因数分解结果的变体

有些题目不仅需要 φ(n) ，还需要知道 n 的质因数分解形式。我们可以稍微修改单点求值函数，使其在计算过程中收集质因子。

// 变体：计算欧拉函数，并返回质因子列表
long long euler_phi_with_factors(long long n, vector<long long>& factors) {
    long long ans = n;
    long long temp = n;
    factors.clear(); // 清空传入的vector
    for (long long p = 2; p * p <= temp; p++) {
        if (temp % p == 0) {
            factors.push_back(p); // 记录质因子
            ans = ans / p * (p - 1);
            while (temp % p == 0) temp /= p;
        }
    }
    if (temp > 1) {
        factors.push_back(temp); // 记录剩余的大质因子
        ans = ans / temp * (temp - 1);
    }
    return ans;
}

这个变体在解决一些更复杂的数论问题时很有用，比如求 n 的原根，就需要知道 φ(n) 的所有质因子。

5.2 处理 n=1 的边界情况

这是一个非常容易忽略的坑！根据定义， φ(1) = 1 （因为 1 和 1 的最大公约数是 1 ，且小于等于 1 的正整数只有 1 本身）。但在我们的单点求值模板中，如果输入 n=1 ， for 循环条件 p*p <= temp 初始就不满足（ 2*2 > 1 ），会直接跳到最后的 if(temp>1) 判断，此时 temp=1 ，不大于 1 ，所以函数返回初始值 ans=n=1 。 看起来结果是正确的，但过程是巧合。 更严谨的写法，应该在函数开头显式处理 n=1 的情况：

long long euler_phi(long long n) {
    if (n == 1) return 1; // 显式处理边界
    long long ans = n;
    // ... 其余代码不变
}

对于预处理模板（线性筛），我们通常会在初始化时设置 phi[1] = 1 。

5.3 大整数与溢出问题

当 n 很大（比如接近 10^18 ）时，我们的单点求值模板中的 p * p <= temp 可能会溢出，即使 p 和 temp 都是 long long 。例如，当 p 很大时（大于 2^31 ）， p * p 可能会超过 64 位有符号整数的范围，导致溢出为负数，从而使循环条件误判。更安全的写法是：

for (long long p = 2; p <= temp / p; p++) { // 用除法代替乘法判断
    if (temp % p == 0) {
        // ...
    }
}

同样，在计算 ans = ans / p * (p - 1) 时，虽然数学上 ans 能被 p 整除，但在代码执行过程中， ans 可能已经因为之前的连乘连除而变得很大或很小。如果题目对模数有要求（比如结果要对一个大质数取模），我们就不能直接使用整数除法，而需要使用 模逆元 来计算 ans = ans * (p-1) * inv(p) % MOD ，其中 inv(p) 是 p 在模 MOD 意义下的乘法逆元。这是数论题中另一个常见的坑点。

5.4 性能优化：使用质数表进行试除

在单点求值中，我们循环 p 从 2 到 √n 。实际上，我们只需要用质数去试除就够了。如果 n 很大，且我们需要多次调用单点求值函数，可以先用线性筛预处理出一个 sqrt(MAX_N) 范围内的质数表，然后在求值函数中只用这些质数去试除，可以显著减少循环次数。

// 假设已经用线性筛得到了 primes[] 数组和 cnt
long long euler_phi_fast(long long n, const int primes[], int cnt) {
    if (n == 1) return 1;
    long long ans = n;
    long long temp = n;
    for (int i = 0; i < cnt; i++) {
        long long p = primes[i];
        if (p * p > temp) break; // 质数的平方大于当前temp，终止
        if (temp % p == 0) {
            ans = ans / p * (p - 1);
            while (temp % p == 0) temp /= p;
        }
    }
    if (temp > 1) {
        ans = ans / temp * (temp - 1);
    }
    return ans;
}

这个优化在 n 很大且随机时效果明显，因为大部分合数在很小的质数阶段就被分解了。

6. 实战应用场景与题目分析

欧拉函数模板不是孤立的，它常常作为子模块嵌入到更复杂的问题中。下面看几个典型场景。

场景一：求解模运算下的乘法逆元（费马小定理） 在模质数 p 的意义下，如果 a 不是 p 的倍数，则 a 的逆元 a^(-1) ≡ a^(p-2) (mod p) 。这里 p-1 就是 φ(p) 。更一般地，根据欧拉定理：如果 gcd(a, n) = 1 ，则 a^φ(n) ≡ 1 (mod n) 。因此， a 在模 n 下的一个逆元是 a^(φ(n)-1) mod n （前提是 a 与 n 互质）。计算 a^b mod n 需要快速幂，而其中指数 b 就可能用到 φ(n) 。

场景二：RSA加密算法 RSA公钥密码体系的核心计算中，关键一步是选择两个大质数 p 和 q ，计算 n = p*q 以及 φ(n) = (p-1)*(q-1) 。然后选择一个与 φ(n) 互质的整数 e 作为公钥，再计算私钥 d 使得 e*d ≡ 1 (mod φ(n)) 。这里， φ(n) 的计算是基础。虽然实际中 p 和 q 已知，直接相乘即可，但原理正是欧拉函数的积性。

场景三：数论函数求和问题 有一类经典问题：求 ∑_{i=1}^{n} φ(i) 或 ∑_{i=1}^{n} gcd(i, n) 。后者可以通过变形转化为欧拉函数求和： ∑_{d|n} d * φ(n/d) 。解决这类问题，往往需要预处理出 φ(1) 到 φ(n) 的所有值（使用线性筛模板），然后求前缀和。例如，求 ∑_{i=1}^{n} φ(i) ，预处理后直接累加即可， O(1) 查询。

一道经典题目分析： “计算 1 <= i, j <= n 的数对 (i, j) 中，有多少对互质（即 gcd(i, j) = 1 ）？” 暴力枚举是 O(n^2) ，不可行。一个巧妙的解法是利用欧拉函数。固定 j ，与 j 互质的 i 的个数就是 φ(j) 。所以答案就是 ∑_{j=1}^{n} φ(j) 。我们只需要用线性筛预处理出 φ(1)...φ(n) 并求和，时间复杂度 O(n) ，预处理后可以 O(1) 回答每个 n 的查询。

7. 从模板到精通：理解本质与举一反三

最后，我想分享几点从“会用模板”到“真正理解”的心得。

第一，理解“积性”是核心。 欧拉函数是积性函数，这是它能被高效计算的根本。许多数论函数（如约数个数、约数和、莫比乌斯函数）都是积性的。线性筛之所以强大，就是因为它能在 O(n) 时间内预处理出所有积性函数的值。其核心递推逻辑（根据最小质因子分情况讨论）是相通的。如果你能彻底理解线性筛求欧拉函数的递推公式，那么理解线性筛求莫比乌斯函数 μ(n) 、约数个数函数 d(n) 等，就会容易得多。

第二，公式 φ(n)=n*Π(1-1/p) 的直观意义。 这个公式可以这样理解：从 1 到 n 这 n 个数中，先去掉所有 p1 的倍数（比例是 1/p1 ），剩下 n*(1-1/p1) 个数；再从剩下的数中去掉所有 p2 的倍数（注意，此时 p2 的倍数有些已经被 p1 去掉了，但比例仍然是 1/p2 ，这是由容斥原理保证的），剩下 n*(1-1/p1)*(1-1/p2) 个数……依次类推。这种“筛法”式的理解，和代码实现中的连乘过程完美对应。

第三，关于“模板”的思考。 本文给出了几个模板，但切忌死记硬背。最重要的是掌握其背后的原理： 通过质因数分解，利用积性函数性质和计算公式。 单点求值的本质是试除法分解质因数；埃氏筛预处理是模拟了每个质因子去筛它的倍数；线性筛预处理则是利用最小质因子进行动态递推。当你遇到一个变种问题，比如需要计算 ∑ φ(d) （ d 是 n 的约数），你知道它等于 n 本身（这是一个重要性质），你就能灵活应对，而不是去生搬硬套某个模板。

在实际编码中，我个人的习惯是：如果只需要单次或少量计算，就用单点求值函数，并加上质数表优化（如果预计算质数表方便的话）；如果需要频繁查询区间内的欧拉函数值，或者需要同时用到质数表，那就毫不犹豫地使用线性筛预处理模板。它代码稍长，但一次构建，终身受益，在复杂的数论问题中尤其省心。