青少年编程知识记录 - 中国剩余定理

2025年10月26日 21:03:34

中国剩余定理

中国剩余定理（Chinese Remainder Theorem，简称 CRT）是数论中用于求解一元线性同余方程组的核心算法，适用于方程组中模数两两互质或不互质的场景，广泛应用于密码学、大数计算等领域。

一、核心概念与定理

1.1 问题定义

给定一元线性同余方程组：

$⎩ ⎨ ⎧ x \equiv a_{1} (mod m_{1}) x \equiv a_{2} (mod m_{2}) ⋮ x \equiv a_{k} (mod m_{k})$

其中

a_{1}, a_{2}, \dots, a_{k}

是余数，

m_{1}, m_{2}, \dots, m_{k}

是模数，求满足所有方程的最小非负整数解

x

。

1.2 两种场景的定理表述

CRT 分为模数两两互质和模数不互质两种场景，后者是前者的扩展（也称为 “扩展中国剩余定理”）。

场景	定理内容	解的存在性
模数两两互质	设 $M = m_{1} \times m_{2} \times \dots \times m_{k}$ ， $M_{i} = M / m_{i}$ ，则方程组存在唯一解： $x = (a_{1} M_{1} M_{1 - 1} + a_{2} M_{2} M_{2 - 1} + \dots + a_{k} M_{k} M_{k - 1}) (mod M)$ ，其中 $M_{i - 1}$ 是 $M_{i}$ 模 $m_{i}$ 的逆元。	一定存在解
模数不互质	逐步合并两个方程 $x \equiv a_{1} (mod m_{1})$ 和 $x \equiv a_{2} (mod m_{2})$ ，合并后方程为 $x \equiv a (mod lcm (m_{1}, m_{2}))$ （ $lcm$ 是最小公倍数）。若合并过程中无解，则原方程组无解。	当且仅当 $g cd (m_{1}, m_{2}) ∣ (a_{2} - a_{1})$ 时，两个方程有解

二、关键前置算法

实现 CRT 需依赖扩展欧几里得算法（用于求逆元和解线性方程），其核心是求解

a x + b y = g cd (a, b)

的整数解。

2.1 扩展欧几里得算法（Exgcd）

cpp
运行
// 扩展欧几里得算法：求解 ax + by = gcd(a, b)// 返回值：gcd(a, b)；x, y 是方程的一组整数解（引用传递）long long exgcd(long long a, long long b, long long &x, long long &y) {      if (b == 0) {          x = 1;          y = 0;          return a;      }      long long g = exgcd(b, a % b, y, x);      y -= (a / b) * x;      return g;}

2.2 求模逆元

当

a

与

m

互质时，

a

的模

m

逆元存在，可通过 Exgcd 求解

a x \equiv 1 (mod m)

得到：

cpp
运行
// 求 a 模 m 的逆元（要求 a 与 m 互质）// 若不存在逆元，返回 -1long long mod_inv(long long a, long long m) {      long long x, y;      long long g = exgcd(a, m, x, y);      if (g != 1) return -1; // a 与 m 不互质，无逆元      return (x % m + m) % m; // 确保逆元为正}

三、代码模板

3.1 场景 1：模数两两互质（经典 CRT）

适用于方程组中所有模数

g cd (m_{i}, m_{j}) = 1

（

i \neq = j

）的情况，效率较高。

cpp
运行
#include <iostream>#include <vector>using namespace std;typedef long long ll;// 扩展欧几里得算法（前置）ll exgcd(ll a, ll b, ll &x, ll &y) {      if (b == 0) {          x = 1, y = 0;          return a;      }      ll g = exgcd(b, a % b, y, x);      y -= (a / b) * x;      return g;}// 求逆元（前置）ll mod_inv(ll a, ll m) {      ll x, y;      ll g = exgcd(a, m, x, y);      if (g != 1) return -1;      return (x % m + m) % m;}// 经典CRT：模数两两互质// 参数：a（余数数组），m（模数数组），k（方程组个数）// 返回值：最小非负解 x；若输入非法（如k=0），返回 -1ll crt_coprime(const vector<ll> &a, const vector<ll> &m, int k) {      if (k == 0) return -1;      ll M = 1; // 所有模数的乘积 M = m1*m2*...*mk      ll res = 0; // 最终解            for (int i = 0; i < k; ++i) {          ll Mi = M / m[i]; // M_i = M / m_i          ll inv_Mi = mod_inv(Mi, m[i]); // M_i 模 m_i 的逆元                    // 累加 a_i * M_i * inv(M_i)，并对 M 取模（防止溢出）          res = (res + a[i] * Mi % M * inv_Mi % M) % M;          M *= m[i]; // 更新 M（下一轮 Mi = 新M / m[i+1]）      }            // 确保解为非负（若res为负，加上M转为正）      return (res % M + M) % M;}// 示例：求解方程组 x≡2(mod3), x≡3(mod5), x≡2(mod7)int main() {      vector<ll> a = {2, 3, 2}; // 余数      vector<ll> m = {3, 5, 7}; // 模数（两两互质）      int k = a.size();            ll x = crt_coprime(a, m, k);      cout << "最小非负解：" << x << endl; // 输出 23      return 0;}

3.2 场景 2：模数不互质（扩展 CRT）

适用于模数任意的情况（包括互质），通过逐步合并两个同余方程实现，是更通用的版本。

cpp
运行
#include <iostream>#include <vector>using namespace std;typedef long long ll;// 扩展欧几里得算法（前置）ll exgcd(ll a, ll b, ll &x, ll &y) {      if (b == 0) {          x = 1, y = 0;          return a;      }      ll g = exgcd(b, a % b, y, x);      y -= (a / b) * x;      return g;}// 合并两个同余方程：x≡a1(mod m1) 和 x≡a2(mod m2)// 返回值：{a, m} 表示合并后的方程 x≡a(mod m)；若无解，返回 {-1, -1}pair<ll, ll> merge(ll a1, ll m1, ll a2, ll m2) {      ll x, y;      ll g = exgcd(m1, m2, x, y); // 求 gcd(m1, m2)            // 检查是否有解：gcd(m1,m2) 必须整除 (a2 - a1)      if ((a2 - a1) % g != 0) {          return {-1, -1};      }            // 计算合并后的模数 m = lcm(m1, m2) = m1*m2 / g      ll m = m1 / g * m2;      // 计算合并后的余数 a（确保 a 非负）      ll a = (a1 + x * (a2 - a1) / g % (m2 / g) * m1 % m) % m;      return {(a + m) % m, m};}// 扩展CRT：模数任意（支持不互质）// 参数：a（余数数组），m（模数数组），k（方程组个数）// 返回值：最小非负解 x；若无解，返回 -1ll crt_general(const vector<ll> &a, const vector<ll> &m, int k) {      if (k == 0) return -1;      ll cur_a = a[0]; // 当前合并后的余数      ll cur_m = m[0]; // 当前合并后的模数            // 逐步合并每个方程      for (int i = 1; i < k; ++i) {          auto [new_a, new_m] = merge(cur_a, cur_m, a[i], m[i]);          if (new_a == -1) return -1; // 合并失败，原方程组无解          cur_a = new_a;          cur_m = new_m;      }            // 确保解为非负      return (cur_a % cur_m + cur_m) % cur_m;}// 示例：求解方程组 x≡1(mod2), x≡2(mod4)（无解）；x≡3(mod4), x≡5(mod6)（有解）int main() {      // 示例1：无解情况      vector<ll> a1 = {1, 2};      vector<ll> m1 = {2, 4};      ll x1 = crt_general(a1, m1, 2);      cout << "方程组1解：" << (x1 == -1 ? "无解" : to_string(x1)) << endl; // 输出 无解            // 示例2：有解情况      vector<ll> a2 = {3, 5};      vector<ll> m2 = {4, 6};      ll x2 = crt_general(a2, m2, 2);      cout << "方程组2解：" << x2 << endl; // 输出 11（最小非负解）      return 0;}

四、应用场景与注意事项

4.1 典型应用

大数表示：将大数拆分为多个小模数的余数，降低计算复杂度（如 RSA 加密中处理大指数）。
同余方程求解：解决多个约束下的整数解问题（如日程安排、资源分配）。
密码学：在椭圆曲线加密、哈希函数等领域中用于简化计算。

4.2 注意事项

数据溢出：由于涉及大数乘法（如经典 CRT 中的 $M = m_{1} m_{2} \dots m_{k}$ ），需使用 long long 类型，必要时用 “快速乘”（模意义下乘法）避免溢出。

快速乘模板（防止 $a \times b$ 溢出）：

cpp
运行
ll qmul(ll a, ll b, ll mod) {      ll res = 0;      a = (a % mod + mod) % mod;      while (b > 0) {          if (b & 1) res = (res + a) % mod;          a = (a + a) % mod;          b >>= 1;      }      return res;}

解的存在性：扩展 CRT 中需检查每一步合并是否有解（即 $g cd (m 1, m 2) ∣ (a 2 - a 1)$ ），无解时需及时返回。
模数合法性：模数 $m_{i}$ 必须为正整数，若输入中有负数，需先转为正（如 $m_{i} = (m_{i} % m o d + m o d) % m o d$ ）。

五、模板选择建议

场景	推荐模板	优点	缺点
模数两两互质	经典 CRT	代码简洁，效率高（时间复杂度 $O (k lo g m)$ ）	仅适用于互质模数，不通用
模数任意（含互质）	扩展 CRT	通用性强，支持所有情况	需逐步合并，效率略低于经典 CRT（仍为 $O (k lo g m)$ ）