云计算百科
云计算领域专业知识百科平台

蓝桥杯·全国青少年信息素养大赛·电子学会Python/C++考级:中国剩余定理解析

进入十一月,青少儿信息学赛事迎来密集备考期,几大标志性比赛的时间节点都已明确。

第十八届蓝桥杯(软件赛 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 为奇数,矛盾)

二、核心考点

  • 同余与剩余系:x ≡ a (mod m) 表示 x−a 能被 m 整除;解在模 M 意义下唯一。
  • 扩展欧几里得求逆元:若 gcd(A, m)=1,则存在 A 在模 m 下的乘法逆元 inv,使 A·inv ≡ 1 (mod m),由 exgcd 求系数得到。
  • 互质版 CRT 构造:M=∏mᵢ,Mᵢ=M/mᵢ,令 tᵢ=Mᵢ 在模 mᵢ 下的逆元,则 x = Σ aᵢ·Mᵢ·tᵢ (mod M)。因为 Mᵢ 模其余模数为 0、模 mᵢ 乘 tᵢ 恰为 1,各项「只在自己那一维贡献 aᵢ」。
  • 通用版 CRT 逐条合并:把两个同余方程 x≡a (mod m)、x≡b (mod n) 合并成一个,反复进行;用裴蜀定理判定无解条件。
  • 无解判定:两式合并时,设 g=gcd(m,n),当且仅当 (b−a) 能被 g 整除时有解,否则矛盾(样例 3 即 g=2 而 b−a=1 不被 2 整除)。
  • 周期是 lcm 不是乘积:互质时 lcm=∏mᵢ;不互质时周期 lcm(m,n)=m/g·n,这是通用版与互质版的关键区别。
  • 溢出与归正:M、aᵢ·Mᵢ·tᵢ 可达 10¹⁸ 量级,C++ 用 __int128 中间量;Python 天然大整数。逆元系数可能为负,必须取模归正到 [0, m)。
  • 三、解法 / 拆解

    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):

  • 把 x 写成 a + m·t,代入第二式要求 a + m·t ≡ b (mod n),即 m·t ≡ b−a (mod n)。
  • 设 g = gcd(m, n)。若 (b−a) % g ≠ 0,无解。
  • 两边同除 g:(m/g)·t ≡ (b−a)/g (mod n/g)。此时 gcd(m/g, n/g)=1,用 exgcd 求 m/g 在模 n/g 下的逆元 inv,则 t = ((b−a)/g · inv) mod (n/g)。
  • 新的 x = a + m·t,新模数 m′ = lcm(m, n) = m/g·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 很大时完全不可行)。

    五、七个易错点

  • 余数未归正:输入 aᵢ 可能 ≥ mᵢ 或为负,先取 a %= m 并归正,否则判定与合并都会错。
  • 逆元系数忘记取模归正:exgcd 返回的 x 常为负数,必须 (x % m + m) % m,否则累加出现负值。
  • 通用版用乘积当周期:不互质时周期是 lcm(m,n)=m/g·n,不是 m·n;写成 m·n 会漏解、周期偏大。
  • 无解判定条件写错:是 (b−a) % g != 0,不是 != 1、也不是漏判;g=gcd(m,n) 而非 gcd 之后的值。
  • 同除 g 后取模的模数:t 的模是 n // g,不是 n;这里写错会导致 t 落在错误剩余系。
  • 中间量溢出:aᵢ·Mᵢ·tᵢ 与 m·t 可超 64 位,C++ 必须用 __int128 承接再取模,直接 long long 相乘会溢出得到错误解。
  • 互质判断前提:互质版构造依赖 mᵢ 两两互质;若题目未保证,必须改用通用版,否则 Mᵢ 与 mᵢ 不互质、逆元不存在(exgcd 返回的 g≠1)。
  • 六、进阶方向

    • 线性同余方程组与 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 内打开,也可复制下方明文链接:

  • 全国青少年信息素养大赛复赛集训题目Python&C++.docx https://pan.quark.cn/s/93995d3cb150
  • 2024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdf https://pan.quark.cn/s/da97b5dbf75d
  • Python背记手册.pdf https://pan.quark.cn/s/7568ae9ca92b
  • Python课程 https://pan.quark.cn/s/a94bf02d00c6
  • 2024信息素养大赛图形化复赛集训题答案3-9 https://pan.quark.cn/s/6ccab7ec3cbc
  • 2025年03月份电子学会考级真题 https://pan.quark.cn/s/4403c4228912
  • 2025全国青少年信息素养大赛赛项说明 https://pan.quark.cn/s/d9d0df4a9f29
  • 青少儿信息素养大赛编程资料 https://pan.quark.cn/s/4ab6bd83be8a
  • 资料持续更新,关注获取最新分享。

    赞(0)
    未经允许不得转载:网硕互联帮助中心 » 蓝桥杯·全国青少年信息素养大赛·电子学会Python/C++考级:中国剩余定理解析
    分享到: 更多 (0)

    评论 抢沙发

    评论前必须登录!