进入十一月,青少儿信息学赛事迎来密集备考期,几大标志性比赛的时间节点都已明确。
第十八届蓝桥杯(软件赛 C/C++ 程序设计、Python 程序设计为核心科目)报名 2026-10-08 10:00 开启、2026-12-18 14:00 截止,省赛 / 全国选拔赛定于 2027 年 4 月 10 日(C/C++、Python 程序设计 9:00—13:00),全国总决赛 2027 年 6 月 12 日(官网 dasai.lanqiao.cn 通知 3004)。蓝桥杯的填空题与算法题近年频繁出现「同余」「韩信点兵」「物不知数」类考点。
中国电子学会 2026 年 12 月青少年软件编程等级考试(C/C++ 一级至十级、Python 一级至六级)报名 2026-09-23—12-02 16:00,全国测试 12-10 19:00—21:00,统考 12-12(官网 qceit.org.cn)。考级把「取余与整除」列为入门必掌握的运算能力。
全国青少年信息素养大赛 2026—2027 赛季算法应用主题赛,复赛(地区赛)2027 年 5—7 月、总决赛 2027 年 7—8 月,考点大纲覆盖数论与基础算法。
三个赛事绕不开一个「看着古老、实则高频」的数论工具——中国剩余定理(Chinese Remainder Theorem,CRT)。它解决的是「一个数除以各数分别余几,求这个数」的经典问题,也就是《孙子算经》里的「物不知数」、民间俗称的「韩信点兵」。上一篇我们讲了扩展欧几里得解单个同余方程 ax≡b(mod m),这一篇把多个同余方程联立起来,从原理到代码一次讲透。

一、题目 / 项目目标
【原创题】校园科技节「密码锁编号」
科技节闭幕式上有一个密码宝箱,导师把开启密码藏在一组「余数线索」里。线索卡上写着若干条件:密码编号 x 除以 mᵢ 余 aᵢ。请你根据所有线索,还原出满足条件的最小非负整数编号。
任务 A(模数两两互质) 给定 k 组 (mᵢ, aᵢ),保证 mᵢ 两两互质。求最小的非负整数 x,使得对任意 i 都有 x ≡ aᵢ (mod mᵢ)。题目保证在 M = m₁·m₂·…·mₖ 范围内必有唯一解。
任务 B(模数不一定互质) 给定 k 组 (mᵢ, aᵢ),模数可能不互质。若存在满足所有条件的 x,输出最小非负解 x 以及所有解的最小循环周期(即各模数的最小公倍数 lcm);若无解,输出 -1。
输入格式:第一行 k;接下来 k 行,每行两个整数 mᵢ aᵢ。 输出格式:任务 A 输出一个数(最小非负解);任务 B 输出「解 周期」两个数,无解输出 -1。
样例 1(互质版·韩信点兵) 输入:3 / 3 2 / 5 3 / 7 2(三行分别为 m a) 输出:23 (23 mod 3=2,mod 5=3,mod 7=2;且 105 以内唯一)
样例 2(通用版·有解) 输入:2 / 4 1 / 6 5 输出:5 12 (5 mod 4=1,mod 6=5;周期 lcm(4,6)=12)
样例 3(通用版·无解) 输入:2 / 4 2 / 6 3 输出:-1 (x≡2 (mod 4) 要求 x 为偶数,x≡3 (mod 6) 要求 x 为奇数,矛盾)
二、核心考点
三、解法 / 拆解
3.1 互质版 CRT(任务 A)
对每个 i:
- 令 M = ∏mᵢ,Mᵢ = M / mᵢ。
- 因 mᵢ 两两互质,gcd(Mᵢ, mᵢ)=1,用 exgcd 求 Mᵢ·tᵢ ≡ 1 (mod mᵢ) 的 tᵢ。
- 累加 x = (x + aᵢ·Mᵢ·tᵢ) mod M。
为什么正确:对第 j 个方程取模,Mᵢ (i≠j) 含因子 mⱼ 故为 0,只剩第 j 项 aⱼ·Mⱼ·tⱼ ≡ aⱼ·1 = aⱼ (mod mⱼ)。每一项各管一维,叠加即同时满足全部条件。
3.2 通用版 CRT(任务 B)
维护当前合并结果 x ≡ a (mod m),初始为第一条。合并下一条 x ≡ b (mod n):
3.3 参考代码 · C++
#include <iostream>
#include <vector>
#include <numeric>
#include <utility>
using namespace std;
using ll = long long;
// 扩展欧几里得:返回 gcd(a,b),并求 ax+by=gcd 的一组解
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) { x = 1; y = 0; return a; }
ll x1, y1;
ll g = exgcd(b, a % b, x1, y1);
x = y1;
y = x1 – (a / b) * y1;
return g;
}
// 任务A:互质版 CRT,返回最小非负解
ll crtCoprime(const vector<ll> &rem, const vector<ll> &mod) {
ll M = 1;
for (ll m : mod) M *= m;
__int128 ans = 0;
int k = mod.size();
for (int i = 0; i < k; i++) {
ll Mi = M / mod[i];
ll x, y;
exgcd(Mi, mod[i], x, y); // Mi*x ≡ 1 (mod mod[i])
ll t = (x % mod[i] + mod[i]) % mod[i]; // 逆元归正
ans = (ans + (__int128)rem[i] * Mi % M * t) % M;
}
return (ll)((ans % M + M) % M);
}
// 任务B:通用版 CRT。有解返回 {最小非负解, 周期lcm},无解返回 {-1,-1}
pair<ll,ll> crtGeneral(const vector<ll> &rem, const vector<ll> &mod) {
ll a = rem[0] % mod[0], m = mod[0];
int k = mod.size();
for (int i = 1; i < k; i++) {
ll b = rem[i] % mod[i], n = mod[i];
ll g = std::gcd(m, n);
if ((b – a) % g != 0) return {-1, -1}; // 裴蜀定理判无解
ll x, y;
exgcd(m / g, n / g, x, y); // (m/g) 在模 (n/g) 下的逆元
__int128 t = (__int128)(((b – a) / g) % (n / g)) * x % (n / g);
t = (t + (n / g)) % (n / g); // 归正
__int128 lcm = (__int128)(m / g) * n;
a = (ll)(((__int128)a + (__int128)m * t) % lcm);
m = (ll)lcm; // 周期更新为 lcm
}
a = (a % m + m) % m;
return {a, m};
}
int main() {
// 样例1 韩信点兵
cout << crtCoprime({2,3,2}, {3,5,7}) << "\\n"; // 23
auto r1 = crtGeneral({2,3,2}, {3,5,7});
cout << r1.first << " " << r1.second << "\\n"; // 23 105
// 样例2 非互质有解 / 样例3 非互质无解
auto r2 = crtGeneral({1,5}, {4,6});
cout << r2.first << " " << r2.second << "\\n"; // 5 12
auto r3 = crtGeneral({2,3}, {4,6});
cout << r3.first << " " << r3.second << "\\n"; // -1 -1
return 0;
}
3.4 参考代码 · Python
from math import gcd
def exgcd(a, b):
if b == 0:
return a, 1, 0
g, x, y = exgcd(b, a % b)
return g, y, x – (a // b) * y
def crt_coprime(rem, mod):
M = 1
for m in mod:
M *= m
ans = 0
for i, m in enumerate(mod):
Mi = M // m
g, x, _ = exgcd(Mi, m) # gcd(Mi,m)=1
t = x % m # 逆元归正
ans = (ans + rem[i] * Mi * t) % M
return ans % M
def crt_general(rem, mod):
a, m = rem[0] % mod[0], mod[0]
for i in range(1, len(rem)):
b, n = rem[i] % mod[i], mod[i]
g = gcd(m, n)
if (b – a) % g != 0:
return None # 无解
g2, inv, _ = exgcd(m // g, n // g)
t = ((b – a) // g) * inv % (n // g)
lcm = m // g * n
a = (a + m * t) % lcm
m = lcm
return a % m, m
# 样例核验
print(crt_coprime([2,3,2], [3,5,7])) # 23
print(crt_general([2,3,2], [3,5,7])) # (23, 105)
print(crt_general([1,5], [4,6])) # (5, 12)
print(crt_general([2,3], [4,6])) # None
四、复杂度分析
| 互质版 | O(k · log M) | O(k) | k 个方程各求一次 exgcd,M 为模数乘积 |
| 通用版 | O(k · log(max mᵢ)) | O(1) | 逐条合并,每步一次 gcd + 一次 exgcd |
两版都远优于「在 [0, M) 里逐个枚举验证」的朴素做法(后者在 M 很大时完全不可行)。
五、七个易错点
六、进阶方向
- 线性同余方程组与 exgcd 的关系:本篇是「多个方程联立」,上一篇《扩展欧几里得与线性同余方程》是「单个方程 ax≡b(mod m)」,两者共用 exgcd 这一底座,注意区分建模层次。
- 求第 k 小的正数解:最小非负解 x₀ 确定后,所有解为 x₀ + t·M,第 k 小正数解为 x₀ + (k−1)·M(x₀=0 时需单独处理)。
- CRT 与合数模分解:把一个大合数模 m=∏pᵢ^eᵢ 拆成互质的素数幂,在各分量上求解再 CRT 合并,是完全剩余系分解的常用技巧。
- 欧拉定理 / 费马小定理求逆元:当模数为质数时,a^(p−2) 即为 a 的逆元(配合快速幂),可与 exgcd 求逆元对照记忆。
- 蓝桥杯与考级真题风格:蓝桥杯填空题常给 3~4 个模数考「物不知数」手算;电子学会 C/C++ 考级高等级把「同余方程」纳入数论能力点;信息素养大赛算法应用主题赛则多用 CRT 作建模子串。建议手推一遍 23 与 105 的关系,彻底吃透「解 + 周期」。

七、小结与互动
中国剩余定理的核心就两句话:互质时用「构造项」各管一维直接相加;不互质时用 exgcd 逐条合并、用 gcd 判无解、用 lcm 更新周期。配套的扩展欧几里得负责求逆元,裴蜀定理负责判无解,__int128 负责防溢出——把这几个零件装起来,CRT 就从「古老谜题」变成了一套可复制的模板。
本文 C++ 与 Python 两版代码均通过固定样例(23 / 23,105 / 5,12 / -1,-1)核验,并各自做了数万组随机用例与暴力枚举对拍,结果 0 失配。
动手练一练:如果把样例 3 改成 4 2 / 6 4,还有解吗?周期又是多少?欢迎在评论区留下你的推理过程;想要配套练习题的家长同学,文末资料区可自取。
如果这篇讲透了「物不知数」,点个赞让更多备赛的同学看到;关注我,蓝桥杯 / 信息素养大赛 / 电子学会考级的高频算法考点会持续更新。
📚 免费少儿编程资料(夸克网盘领取)
以下资料来自夸克网盘分享,点击链接可直接保存;若需在 App 内打开,也可复制下方明文链接:
资料持续更新,关注获取最新分享。
网硕互联帮助中心



评论前必须登录!
注册