当前位置：首页 > C++知识 > 正文内容

中国剩余定理

亿万年的星光8小时前C++知识5

中国剩余定理（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)$ ）

扫描二维码推送至手机访问。

分享给朋友：

返回列表

上一篇：多重背包问题

没有最新的文章了...

【贪心】区间选点

【题目描述】数轴上有n个闭区间[ai, bi]，取尽量少的点，使得每个区间内都至少有一个点。（不同区间内含的点可以是同一个，1<=n<=10000，1<=ai<=bi<=...

拓扑排序

一、定义对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则...

指针（三）：指针与函数

1.交换的例子#include<iostream> #include<cstdio> #include<cstring> using namespa...

01背包问题

问题定义01背包问题是一个经典的组合优化问题，通常描述如下：有个容量为C的背包有n件物品，第i件物品的重量为Wi,价值为Vi每种物品只有一件，可以选择放入背包（1）或不放入背包（0），因此称为“01”...

如何估算时间复杂度

首先：常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n^2)＜Ο(n^3)＜…＜Ο(2^n)＜Ο(n!)时间复杂度可以简单理解为最多执...

【题解】盈亏问题

【题目描述】一群人团购一件物品：如果每人出 a元，所付总金额比物价多出了x 元；如果每人少出 1元，也就是每人出a-1元，所付总金额比物价少了y元。给定 a,x,y求参与团购的人数及该物品的...

青少年编程知识记录

中国剩余定理

一、核心概念与定理

1.1 问题定义

1.2 两种场景的定理表述

二、关键前置算法

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

2.2 求模逆元

三、代码模板

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

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

四、应用场景与注意事项

4.1 典型应用

4.2 注意事项

五、模板选择建议

相关文章

【贪心】区间选点

拓扑排序

指针（三）：指针与函数

01背包问题

如何估算时间复杂度

【题解】盈亏问题

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.

青少年编程知识记录

中国剩余定理

一、核心概念与定理

1.1 问题定义

1.2 两种场景的定理表述

二、关键前置算法

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

2.2 求模逆元

三、代码模板

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

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

四、应用场景与注意事项

4.1 典型应用

4.2 注意事项

五、模板选择建议

相关文章

【贪心】区间选点

拓扑排序

指针（三）：指针与函数

01背包问题

如何估算时间复杂度

【题解】盈亏问题

鲁ICP备20008475号var _hmt = _hmt || [];(function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?bf4de1f8c92c90db1ab8165f21fb936d"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s);})();

Powered By Z-BlogPHP. Theme by TOYEAN.

鲁ICP备20008475号