C++数论入门：从欧几里得到中国剩余定理

在C++算法竞赛中，数论是一个让很多人又爱又恨的领域。爱的是它背后的数学之美，恨的是那些铺天盖地的取模运算、逆元、同余方程。但如果你愿意静下心来，你会发现数论其实有一条非常清晰的主线：从最古老的欧几里得算法开始，一步步走到中国剩余定理——这两个跨越两千年的智慧，至今仍在密码学、编码理论和算法设计中熠熠生辉。

本文将从零开始，用 C++ 代码带你实现数论中最核心的几个算法：欧几里得算法、扩展欧几里得算法、模逆元的求解、以及中国剩余定理（CRT）。全文约 2000 字，适合具备基础 C++ 语法、但对数论感到陌生的读者。

一、欧几里得算法：辗转相除法的魅力

欧几里得算法（Euclidean Algorithm）是求两个整数最大公约数（GCD）的最古老、最有效的算法。它的原理极其简单：

gcd(a, b) = gcd(b, a mod b)

反复运用这个等式，直到余数为 0，此时的除数就是最大公约数。

C++ 实现（递归与迭代）

// 递归写法（简洁）
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 迭代写法（防止递归深度过大）
int gcd(int a, int b) {
    while (b) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

这段代码可以处理负数吗？可以，因为 a % b 在 C++ 中结果的符号与被除数相同，但最终绝对值上的最大公约数仍然正确。通常我们会取绝对值：gcd(abs(a), abs(b))。

时间复杂度

欧几里得算法的时间复杂度为 O(log min(a, b))，即使在 64 位整数范围内也能飞快运行。

一个拓展：最小公倍数（LCM）

有了 GCD，LCM 可以直接计算：

int lcm(int a, int b) {
    return a / gcd(a, b) * b;   // 先除后乘，防止溢出
}

二、扩展欧几里得算法：求解不定方程

扩展欧几里得算法（Extended Euclidean Algorithm）不仅求出 gcd(a, b)，还能找到一组整数解 (x, y) 使得：

a·x + b·y = gcd(a, b)

这个等式被称为 贝祖等式。它在求解模逆元、解一次同余方程时至关重要。

原理推导

当 b = 0 时，gcd(a, 0) = a，此时解为 x = 1, y = 0。
当 b > 0 时，我们有：

gcd(a, b) = gcd(b, a mod b)

假设我们已经求出了下一层的解 (x₁, y₁)，使得：

b·x₁ + (a mod b)·y₁ = gcd(b, a mod b) = gcd(a, b)

而 a mod b = a - floor(a/b)·b，代入并整理，最终得到：

x = y₁
y = x₁ - floor(a/b)·y₁

这就是递归回溯时的更新公式。

C++ 实现

// 返回 gcd(a,b)，并将 x, y 设置为满足 ax + by = gcd(a,b) 的一组解
int extended_gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return d;
}

测试一下：求 35 和 15 的贝祖等式解。

int x, y;
int g = extended_gcd(35, 15, x, y);
// g = 5, x = 1, y = -2 → 35*1 + 15*(-2) = 35 - 30 = 5 ✅

应用一：求解线性同余方程

线性同余方程形如：a·x ≡ b (mod m)。它有解当且仅当 gcd(a, m) | b。解可以通过扩展欧几里得求出：

1. 先用扩展欧几里得求 a·x0 + m·y0 = gcd(a, m)。

2. 两边乘以 b / g，得到 a·(x0 * (b/g)) ≡ b (mod m)。

3. 模 m 下的解为 x = (x0 * (b/g) % m + m) % m。

C++ 实现：

// 求解 a*x ≡ b (mod m)，返回最小非负整数解，若无解返回 -1
int linear_congruence(int a, int b, int m) {
    int x, y;
    int g = extended_gcd(a, m, x, y);
    if (b % g != 0) return -1;
    int x0 = x * (b / g) % m;
    if (x0 < 0) x0 += m;
    return x0;
}

三、模逆元：除法在模世界中的化身

在模运算中，我们无法直接做除法，而是乘以“逆元”。如果 a·x ≡ 1 (mod m)，则 x 称为 a 在模 m 下的逆元，记作 a⁻¹。

逆元存在的条件

gcd(a, m) = 1，即 a 与 m 互质。

求逆元的方法

方法一：扩展欧几里得（通用）

int mod_inverse(int a, int m) {
    int x, y;
    int g = extended_gcd(a, m, x, y);
    // 要求 a 和 m 互质，否则不存在逆元
    if (g != 1) return -1;
    return (x % m + m) % m;   // 保证为正
}

方法二：费马小定理（m 为素数时）

如果 m 是素数，则 a^(m-2) ≡ a⁻¹ (mod m)，可以用快速幂在 O(log m) 时间内求解。

int mod_pow(int a, int b, int mod) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1LL * res * a % mod;
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return res;
}

int mod_inverse_prime(int a, int p) {
    return mod_pow(a, p-2, p);
}

四、中国剩余定理（CRT）：古老智慧的现代应用

中国剩余定理解决的是如下问题：给定一组两两互质的模数 m₁, m₂, …, m_k，以及相应的余数 r₁, r₂, …, r_k，求整数 x 满足：

x ≡ r₁ (mod m₁)
x ≡ r₂ (mod m₂)
...
x ≡ rₖ (mod mₖ)

在模 M = m₁·m₂·…·mₖ 下有唯一解。

构造解法（公式法）

1. 计算 M = ∏ mᵢ。

2. 对每个方程，计算 Mᵢ = M / mᵢ。

3. 求 Mᵢ 在模 mᵢ 下的逆元 invᵢ，使得 Mᵢ·invᵢ ≡ 1 (mod mᵢ)（因为 mᵢ 互质，逆元存在）。

4. 则解为 x = (∑ rᵢ·Mᵢ·invᵢ) mod M。

C++ 实现

// 要求 mod[] 中元素两两互质，rem[] 是对应的余数，k 是方程个数
int crt(int rem[], int mod[], int k) {
    int M = 1;
    for (int i = 0; i < k; ++i) M *= mod[i];
    int result = 0;
    for (int i = 0; i < k; ++i) {
        int Mi = M / mod[i];
        int inv = mod_inverse(Mi, mod[i]);   // 扩展欧几里得求逆元
        result = (result + 1LL * rem[i] * Mi % M * inv) % M;
    }
    return result;
}

例子

解方程组：

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

M = 3×5×7 = 105
i=0: M₁=35, inv₁=2 (因为 35 mod 3 = 2, 2×2=4≡1 mod3) → 贡献 2×35×2=140
i=1: M₂=21, inv₂=1 (21 mod5=1) → 贡献 3×21×1=63
i=2: M₃=15, inv₃=1 (15 mod7=1) → 贡献 2×15×1=30
总和 = 140+63+30=233，233 mod 105 = 23。验证：23 mod 3 = 2, mod 5 = 3, mod 7 = 2 ✅

五、扩展到非互质模数的中国剩余定理

当模数 mᵢ 不互质时，标准 CRT 不再适用。此时需要两两合并方程。思路是：

假设已有方程 x ≡ r1 (mod m1) 和 x ≡ r2 (mod m2)，我们设 x = r1 + t·m1，代入第二个方程得到：

r1 + t·m1 ≡ r2 (mod m2)  →  m1·t ≡ r2 - r1 (mod m2)

这是一个线性同余方程，用扩展欧几里得判断是否有解。若有解，则合并后的新模数为 lcm(m1, m2)，新余数为 r1 + t·m1 模 lcm。

重复合并所有方程即可。这是竞赛中处理一般模数 CRT 的标准做法，代码略长，但思路清晰。

六、数论算法在 C++ 中的注意事项

1. 整数溢出：在计算 M = ∏ mᵢ 时，可能超过 64 位整数范围（比如 mᵢ 都是 1e9 量级）。竞赛中通常会在模另一个数下进行，或者使用 __int128 或 Python 大整数。

2. 负数取模：C++ 的 % 对负数结果为负，应调整为 (x % mod + mod) % mod。

3. 效率：扩展欧几里得 O(log n)，CRT 中求逆元 O(log m)，总复杂度很低。

4. 使用 C++17 的 [[nodiscard]]：可以对重要函数标记，提醒检查返回值（如逆元是否存在）。

七、实战题目推荐

学完这些理论，你需要通过题目巩固。以下为推荐的练习路径：

• 基础GCD：洛谷 P1029 最大公约数和最小公倍数问题

• 扩展欧几里得：洛谷 P1082 同余方程（求逆元）

• 中国剩余定理：洛谷 P1495 曹冲养猪（标准 CRT）

• 非互质 CRT：洛谷 P4777 扩展中国剩余定理（EXCRT）

完成这些题目，你对数论入门模块就有了扎实的理解。

八、总结

从欧几里得辗转相除，到扩展欧几里得求解不定方程，再到模逆元和解决同余方程组，这是一条环环相扣的知识链。中国剩余定理不仅是一个古老的数学技巧，更是现代密码学（RSA 解密加速）、快速傅里叶变换（FFT）中用到的重要工具。

C++ 的高效整数运算和模板化能力，使得实现这些数论算法变得简洁而优雅。当你第一次用自己写的扩展欧几里得解出一道线性同余方程时，那种成就感会帮你跨过数论的第一道门槛。

数论是无穷的宝藏，本文只是揭开了它的冰山一角。接下来，你可以走向欧拉函数、原根、莫比乌斯反演……愿你在数论的旅途中，享受数学与代码碰撞的美妙火花。