【算法基础篇】（四十二）数论之欧拉函数深度精讲：从互质到数论应用

前言

在算法竞赛的数论领域，欧拉函数是连接 “互质” 与 “实际问题” 的关键桥梁。它看似抽象 —— 统计 1 到 n 中与 n 互质的数的个数，但背后藏着巧妙的数学逻辑和高效的计算方法。无论是仪仗队视线问题、GCD 计数问题，还是后续的欧拉降幂、同余方程求解，欧拉函数都扮演着核心角色。本文将从互质概念切入，层层拆解欧拉函数的定义、性质、计算方法，结合洛谷经典例题，手把手教你掌握从单个函数计算到批量打表的全流程，让你在数论题目中轻松举一反三。下面就让我们正式开始吧！

一、欧拉函数的核心概念：什么是 φ(n)？

1.1 互质的定义

在理解欧拉函数之前，我们先明确 “互质” 的概念：若两个整数 a 和 b 的最大公约数为 1（即 gcd (a,b)=1），则称 a 和 b 互质（也称互素）。例如，5 和 8 互质（gcd (5,8)=1），而 6 和 9 不互质（gcd (6,9)=3）。

特别注意：

• 1 与任何整数都互质（因为 gcd (1,x)=1）；
• 质数 p 与所有小于 p 的正整数都互质（质数的约数只有 1 和自身）；
• 互质的两个数不一定都是质数（如 8 和 9 都是合数，但它们互质）。

1.2 欧拉函数的定义

欧拉函数 φ(n)（读作 “phi (n)”）表示：在整数 1 到 n 的范围内，与 n 互质的数的个数。

举几个直观例子：

• φ(1)=1：1 到 1 中，与 1 互质的数只有 1 本身；
• φ(2)=1：1 到 2 中，与 2 互质的数是 1；
• φ(3)=2：1 到 3 中，与 3 互质的数是 1、2；
• φ(4)=2：1 到 4 中，与 4 互质的数是 1、3；
• φ(5)=4：1 到 5 中，与 5 互质的数是 1、2、3、4；
• φ(6)=2：1 到 6 中，与 6 互质的数是 1、5（gcd (1,6)=1，gcd (5,6)=1）。

通过这些例子可以发现：质数 p 的欧拉函数 φ(p)=p-1（因为所有小于 p 的数都与 p 互质），这是欧拉函数的一个重要特殊情况。

1.3 欧拉函数的数学表达式

根据算术基本定理，任何大于 1 的自然数 n 都可以唯一分解为质因数的乘积：n=p1α1​​×p2α2​​×⋯×pkαk​​其中 p₁<p₂<…<p_k 是质数，α₁、α₂、…、α_k 是正整数。

欧拉函数的数学表达式为：φ(n)=n×(1−p1​1​)×(1−p2​1​)×⋯×(1−pk​1​)

这个公式的核心思想是 “容斥原理”：从 n 个数字中，依次排除能被每个质因子 p_i 整除的数，最终剩下的就是与 n 互质的数。

举个例子，计算 φ(12)：

1. 12 的质因数分解为 12=2²×3¹；
2. 代入公式：φ(12)=12×(1-1/2)×(1-1/3)=12×1/2×2/3=4；
3. 验证：1 到 12 中与 12 互质的数是 1、5、7、11，共 4 个，与计算结果一致。

二、欧拉函数的重要性质：解题的关键抓手

欧拉函数的性质是解决复杂问题的核心，掌握这些性质能让你在解题时事半功倍。

2.1 性质 1：若 p 是质数，则 φ(p)=p-1

这是最基础的性质，前面已经举例说明。因为质数 p 的约数只有 1 和 p，所以 1 到 p 中与 p 互质的数是所有小于 p 的正整数，共 p-1 个。

2.2 性质 2：若 p 是质数，k 是正整数，则 φ(pᵏ)=(p-1)×pᵏ⁻¹

推导过程：

• pᵏ的质因数只有 p，根据欧拉函数公式：φ(pᵏ)=pᵏ×(1-1/p)=pᵏ - pᵏ⁻¹=(p-1)×pᵏ⁻¹；
• 例子：φ(8)=φ(2³)=(2-1)×2²=4（1 到 8 中与 8 互质的数是 1、3、5、7，共 4 个）。

2.3 性质 3：欧拉函数是积性函数

若 a 和 b 互质（gcd (a,b)=1），则 φ(a×b)=φ(a)×φ(b)。

这是欧拉函数最重要的性质，也是批量计算欧拉函数的核心依据。

例子：

• φ(6)=φ(2×3)=φ(2)×φ(3)=1×2=2（与之前的计算一致）；
• φ(15)=φ(3×5)=φ(3)×φ(5)=2×4=8（1 到 15 中与 15 互质的数是 1、2、4、7、8、11、13、14，共 8 个）。

2.4 性质 4：若 n 是偶数，则 φ(2n)=φ(n)（当 n 为奇数时）

推导：因为 n 是奇数，所以 2 和 n 互质，根据积性函数性质：φ(2n)=φ(2)×φ(n)=1×φ(n)=φ(n)。

例子：φ(6)=φ(2×3)=φ(3)=2（3 是奇数），与实际结果一致。

2.5 性质 5：对于任意正整数 n，有 n=Σφ(d)（d 是 n 的所有正约数）

这是欧拉函数的一个重要恒等式，表示 n 等于其所有正约数的欧拉函数之和。

例子：n=6 的正约数是 1、2、3、6，Σφ(d)=φ(1)+φ(2)+φ(3)+φ(6)=1+1+2+2=6，与 n 相等。

这个性质在后续的数论问题中（如 GCD 计数）会经常用到，需要重点记忆。

三、欧拉函数的计算方法：从单个到批量

3.1 方法一：试除法计算单个欧拉函数

根据欧拉函数的数学表达式，计算单个数字 n 的 φ(n) 可以按照以下步骤：

1. 对 n 进行质因数分解，得到所有不同的质因子 p₁、p₂、…、p_k；
2. 代入公式 φ(n)=n×(1-1/p₁)×(1-1/p₂)×…×(1-1/p_k)；
3. 计算时注意 “先除后乘”，避免整数溢出。

代码实现（试除法）

#include <iostream>
using namespace std;

typedef long long LL;

// 试除法计算单个数字的欧拉函数
LL phi(LL n) {
    LL res = n; // 初始值为n
    // 枚举质因子，直到sqrt(n)
    for (LL i = 2; i <= n / i; ++i) {
        if (n % i == 0) { // i是n的质因子
            // 应用公式：res = res * (i-1) / i
            res = res / i * (i - 1);
            // 除尽所有i的倍数，避免重复计算
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    // 若剩余n>1，说明是最后一个质因子
    if (n > 1) {
        res = res / n * (n - 1);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    LL n;
    while (cin >> n) {
        cout << "φ(" << n << ") = " << phi(n) << endl;
    }
    return 0;
}

代码分析

• 时间复杂度：O (√n)，与试除法分解质因数的时间复杂度一致；
• 溢出处理：使用 LL（long long）存储结果，避免 n 较大时溢出；“先除后乘”（如 res = res /i * (i-1)）确保中间结果是整数，避免小数误差；
• 边界处理：n=1 时，返回 1（因为 φ(1)=1）；n 为质数时，最后会执行if(n>1)分支，返回 res = n * (n-1)/n = n-1，符合性质 1。

测试用例

• 输入：6 → 输出：φ(6) = 2
• 输入：12 → 输出：φ(12) = 4
• 输入：7 → 输出：φ(7) = 6（7 是质数）
• 输入：1 → 输出：φ(1) = 1

3.2 方法二：欧拉筛（线性筛）批量计算欧拉函数

当需要计算 1 到 n 范围内所有数字的欧拉函数时，试除法的时间复杂度为 O (n√n)，对于 n=1e6 等大规模数据会超时。此时需要更高效的方法 —— 结合欧拉筛（线性筛），在 O (n) 时间内批量计算欧拉函数。

核心思路

欧拉筛的核心是 “让每个合数只被其最小质因子筛掉”，结合欧拉函数的性质，我们可以在筛质数的同时递推计算每个数的 φ 值：

1. 若 i 是质数（未被标记）：φ(i)=i-1（性质 1）；
2. 若 i 是合数，设 p_j 是 i 的最小质因子（即 i = p_j × k）：
   • 若 p_j 是 k 的质因子（i % p_j == 0）：则 φ(i) = φ(k × p_j) = p_j × φ(k)（因为 p_j 是 k 的质因子，i 的质因子与 k 完全相同，根据欧拉函数公式推导）；
   • 若 p_j 不是 k 的质因子（i % p_j != 0）：则 k 与 p_j 互质，根据积性函数性质，φ(i)=φ(k) × φ(p_j)=φ(k) × (p_j - 1)。

代码实现（欧拉筛批量计算）

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1e6 + 10;
bool st[MAXN]; // 标记是否为合数
int primes[MAXN], cnt; // 存储质数，cnt为质数个数
int phi[MAXN]; // 存储欧拉函数值

// 欧拉筛批量计算1~n的欧拉函数
void get_phi(int n) {
    memset(st, false, sizeof st);
    memset(phi, 0, sizeof phi);
    cnt = 0;
    phi[1] = 1; // 特殊情况：φ(1)=1
    for (int i = 2; i <= n; ++i) {
        if (!st[i]) { // i是质数
            primes[++cnt] = i;
            phi[i] = i - 1; // 性质1：质数的欧拉函数为i-1
        }
        // 枚举所有已找到的质数，筛掉i*primes[j]
        for (int j = 1; 1LL * i * primes[j] <= n; ++j) {
            int x = i * primes[j];
            st[x] = true; // 标记为合数
            if (i % primes[j] == 0) { // primes[j]是i的最小质因子，且是i的质因子
                phi[x] = phi[i] * primes[j];
                break;
            } else { // primes[j]是i的最小质因子，但不是i的质因子（i与primes[j]互质）
                phi[x] = phi[i] * (primes[j] - 1);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n = 1e6;
    get_phi(n);
    
    // 输出1~10的欧拉函数值
    for (int i = 1; i <= 10; ++i) {
        cout << "φ(" << i << ") = " << phi[i] << endl;
    }
    return 0;
}

代码分析

• 时间复杂度：O (n)，每个数只被筛一次，递推计算 φ 值的操作是 O (1)；
• 空间复杂度：O (n)，需要存储质数数组、标记数组和欧拉函数数组，对于 n=1e6，空间占用约 4MB（int 数组），完全可行；
• 递推逻辑验证：
  • 以 i=4（合数）为例，primes [j]=2（最小质因子），i%2==0，phi [4]=phi [2]×2=1×2=2（正确）；
  • 以 i=6（合数）为例，primes [j]=2（最小质因子），i%2!=0（6=2×3，3 与 2 互质），phi [6]=phi [3]×(2-1)=2×1=2（正确）；
  • 以 i=12（合数）为例，primes [j]=2（最小质因子），i%2==0，phi [12]=phi [6]×2=2×2=4（正确）。

应用场景

批量计算欧拉函数适用于以下场景：

• 多次查询 1~n 范围内的欧拉函数值；
• 解决需要用到多个数的欧拉函数的问题（如仪仗队、GCD 计数等）。

四、实战例题 1：洛谷 P2158 仪仗队

题目链接：https://www.luogu.com.cn/problem/P2158

4.1 题目分析

题目描述：仪仗队是由 N×N 的学生组成的方阵，C 君站在方阵的左后方（坐标 (0,0)），视线沿直线延伸。当且仅当学生站在坐标 (i,j)（1≤i,j≤N）且 i 和 j 互质时，C 君才能看到该学生。求 C 君能看到的学生总数。

输入：一行一个正整数 N（N≤40000）。

输出：一行一个整数，表示能看到的学生人数。示例：输入 4 → 输出 9。

核心思路：

• 坐标 (i,j) 能被看到的条件是 gcd (i,j)=1；
• 方阵关于直线 y=x 对称，因此可以先计算上三角（i<j）的数量，乘以 2 后加上对角线上的数量（i=j 时，只有 gcd (i,i)=i=1 时能被看到，即 i=j=1）；
• 上三角（i<j）中，对于每个 i，j 的范围是 i+1 到 N，满足 gcd (i,j)=1 的 j 的个数为 φ(i)（因为 j 可以表示为 i+k，k 从 1 到 N-i，gcd (i,i+k)=gcd (i,k)，所以等价于 k 从 1 到 N-i 中与 i 互质的数的个数，当 N 足够大时，就是 φ(i)）；
• 综上，总人数 = 2×Σφ(i)（i 从 1 到 N-1） + 1（当 N≥1 时）。

4.2 代码实现

#include <iostream>
using namespace std;

typedef long long LL;
const int MAXN = 40010;
bool st[MAXN];
int primes[MAXN], cnt;
int phi[MAXN];

// 欧拉筛批量计算欧拉函数
void get_phi(int n) {
    memset(st, false, sizeof st);
    memset(phi, 0, sizeof phi);
    cnt = 0;
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!st[i]) {
            primes[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; 1LL * i * primes[j] <= n; ++j) {
            int x = i * primes[j];
            st[x] = true;
            if (i % primes[j] == 0) {
                phi[x] = phi[i] * primes[j];
                break;
            } else {
                phi[x] = phi[i] * (primes[j] - 1);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    if (N == 1) { // 特殊情况：1×1方阵，只能看到自己（但题目中坐标是(1,1)？根据示例，N=1时输出0）
        cout << 0 << endl;
        return 0;
    }
    get_phi(N - 1); // 计算1~N-1的欧拉函数
    LL sum = 0;
    for (int i = 1; i < N; ++i) {
        sum += phi[i];
    }
    cout << sum * 2 + 1 << endl; // 对称×2 + 对角线(1,1)
    return 0;
}

4.3 代码验证

以 N=4 为例：

• 计算 1~3 的欧拉函数：φ(1)=1，φ(2)=1，φ(3)=2；
• sum=1+1+2=4；
• 总人数 = 4×2+1=9，与示例输出一致。

4.4 优化说明

• N=1 时输出 0：因为 (1,1) 的 gcd (1,1)=1，但根据题目场景，C 君站在左后方，可能看不到自己，所以特殊处理；
• 时间复杂度：O (N)，欧拉筛计算 φ 值的时间为 O (N)，求和时间为 O (N)，对于 N=4e4 完全可以瞬间完成；
• 空间复杂度：O (N)，数组占用约 160KB（4e4×4 字节），无压力。

五、实战例题 2：洛谷 P2568 GCD

题目链接：https://www.luogu.com.cn/problem/P2568

5.1 题目分析

题目描述：给定正整数 n，求 1≤x,y≤n 且 gcd (x,y) 为质数的数对 (x,y) 的个数。

输入：一行一个正整数 n（n≤1e7）。

输出：一行一个整数，表示满足条件的数对个数。示例：输入 4 → 输出 4。

核心思路：

• 设 gcd (x,y)=d（d 为质数），则可以令 x=d×a，y=d×b，其中 gcd (a,b)=1（因为 d 是最大公约数）；
• 由于 x≤n，y≤n，所以 a≤n/d，b≤n/d；
• 因此，满足条件的数对 (x,y) 的个数，等于所有质数 d 对应的 “1≤a,b≤k（k=n/d）且 gcd (a,b)=1” 的数对个数之和；
• 而 “1≤a,b≤k 且 gcd (a,b)=1” 的数对个数为 2×Σφ(i)（i=1 到 k） - 1（对称 ×2，减去重复计算的 (a,a) 情况）；
• 综上，步骤如下：
  1. 筛选 1~n 的所有质数；
  2. 批量计算 1~n 的欧拉函数，并预处理前缀和数组 f [k] = Σφ(i)（i=1 到 k）；
  3. 对于每个质数 d，计算 k=n/d，贡献为 2×f [k] - 1；
  4. 所有质数的贡献之和即为答案。

5.2 代码实现

#include <iostream>
using namespace std;

typedef long long LL;
const int MAXN = 1e7 + 10;
bool st[MAXN];
int primes[MAXN], cnt;
int phi[MAXN];
LL f[MAXN]; // f[k] = φ(1) + φ(2) + ... + φ(k)

// 欧拉筛批量计算欧拉函数和前缀和
void get_phi_and_prefix(int n) {
    memset(st, false, sizeof st);
    memset(phi, 0, sizeof phi);
    cnt = 0;
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!st[i]) {
            primes[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; 1LL * i * primes[j] <= n; ++j) {
            int x = i * primes[j];
            st[x] = true;
            if (i % primes[j] == 0) {
                phi[x] = phi[i] * primes[j];
                break;
            } else {
                phi[x] = phi[i] * (primes[j] - 1);
            }
        }
    }
    // 计算前缀和f[k]
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i - 1] + phi[i];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    get_phi_and_prefix(n);
    
    LL ans = 0;
    // 遍历所有质数d，计算贡献
    for (int i = 1; i <= cnt; ++i) {
        int d = primes[i];
        int k = n / d;
        ans += 2 * f[k] - 1;
    }
    cout << ans << endl;
    return 0;
}

5.3 代码验证

以 n=4 为例：

• 1~4 的质数为 2、3；
• 前缀和 f [1]=1，f [2]=1+1=2，f [3]=2+2=4，f [4]=4+2=6；
• 对于 d=2：k=4/2=2，贡献 = 2×f [2]-1=2×2-1=3；
• 对于 d=3：k=4/3=1，贡献 = 2×f [1]-1=2×1-1=1；
• 总贡献 = 3+1=4，与示例输出一致。

5.4 优化说明

• 时间复杂度：O (n)，欧拉筛和前缀和计算均为 O (n)，遍历质数的时间为 O (π(n))（π(n) 是 n 以内的质数个数，n=1e7 时约 664579 个），整体效率极高；
• 空间优化：对于 n=1e7，int 数组占用约 40MB（phi 数组）+ 8MB（f 数组）+ 4MB（primes 数组）+ 1MB（st 数组），合计约 53MB，在竞赛允许的内存范围内；
• 溢出处理：使用 LL 存储前缀和和答案，避免 n 较大时溢出。

六、欧拉函数的常见误区与避坑指南

6.1 数值溢出问题

• 计算单个欧拉函数时，未使用 long long 导致溢出（如 n=1e12 时，n×(p-1) 可能超过 int 范围）；
• 批量计算时，前缀和数组未使用 long long（如 n=1e7 时，前缀和可能超过 int 范围）；
• 避坑方案：所有涉及欧拉函数计算和求和的变量，统一使用 long long。

6.2 边界条件处理

• 忘记 φ(1)=1（1 与所有数互质，包括自身）；
• N=1 时的特殊处理（如仪仗队问题中，N=1 输出 0）；
• 质数判断错误（如将 1 误认为质数，导致 φ(1) 计算错误）。

6.3 递推逻辑错误

• 欧拉筛中，混淆 “i% primes [j]==0” 和 “i% primes [j]!=0” 的递推公式；
• 避坑方案：牢记 “若 primes [j] 是 i 的质因子，则 φ(i×primes [j])=primes [j]×φ(i)；否则 φ(i×primes [j])=(primes [j]-1)×φ(i)”。

6.4 效率优化误区

• 对于大规模数据（n=1e6），使用试除法逐个计算欧拉函数（时间复杂度 O (n√n)，会超时）；
• 避坑方案：优先使用欧拉筛批量计算，时间复杂度 O (n)，效率提升显著。

七、欧拉函数的延伸应用

7.1 欧拉降幂（扩展欧拉定理）

欧拉函数是欧拉降幂的核心，用于处理大指数幂取模问题。扩展欧拉定理指出：对于任意整数 a、m 和正整数 b，有：

a^{b}\equiv \left\{\begin{matrix} a^{b} \; mod\; m\; \; \; \; b<\varphi (m)\\ a^{b} \; mod\; m\; \; \; \;b\geqslant \varphi (m) \end{matrix}\right.

应用场景：当 b 极大时（如 b=1e18），直接计算 a^b mod m 是不可能的，此时可以用欧拉降幂将指数缩小。

7.2 同余方程求解

在解同余方程 ax≡1 (mod m) 时，若 a 和 m 互质，则方程的解为 a 的乘法逆元，而根据欧拉定理，a^(φ(m)-1) mod m 就是 a 的一个逆元（因为 a^φ(m)≡1 (mod m)，两边除以 a 得 a^(φ(m)-1)≡a^(-1)(mod m)）。

7.3 数论计数问题

除了本文介绍的 GCD 计数、仪仗队问题，欧拉函数还常用于以下计数场景：

• 统计 1~n 中与 n 互质的数的和（和为 n×φ(n)/2）；
• 计算满足 gcd (x,y)=k 的数对 (x,y) 的个数（转化为 gcd (x/k,y/k)=1 的个数）。

总结

欧拉函数是数论中极具实用性的函数，其核心是 “统计互质数的个数”，但通过性质推导和算法优化，能解决一系列复杂的竞赛问题。 在实际竞赛中，欧拉函数往往不是孤立出现的，而是与质数、GCD、同余方程、降幂等知识点结合考查。因此，除了掌握本文的内容，还需要多做综合性题目，加深对欧拉函数性质的理解，提升知识的融会贯通能力。 如果你在学习过程中遇到具体题目无法解决，或者想进一步了解欧拉降幂、同余方程等延伸知识点，可以随时留言交流。后续将持续更新数论进阶内容，敬请关注！