1. 题目拆解与考点定位1.1 这道题到底在问什么寻找整数这道题从标题上的算法标签就能看出它的真实身份数论里的同余方程求解问题而且点名了扩展欧几里得和中国剩余定理两个关键工具。但我先泼一盆冷水如果你以为这只是套一个中国剩余定理模板就能过的题那大概率会在赛场上翻车。蓝桥杯的省赛题尤其到了Python B组的中后段题位很少会直接给你一份模数两两互质、直接套CRT的裸题。它既然加上了普及的难度标签就一定在经典模型之外埋了需要你自己发现的细节。这类题的核心叙述逻辑通常是这样的给定若干组形如某个数除以a余b的条件让你求满足所有条件的最小正整数或者某个范围内的解。看起来像是小学奥数里韩信点兵的升级版但实际上它真正考察的是你能否在考场上快速识别出这是一个线性同余方程组并且知道在模数不互质时不能无脑使用标准中国剩余定理。1.2 为什么它值得专门写一篇省赛Python组的题难度定级为普及其实非常微妙。它比纯入门模板题多了一层思考但又没有到省选那种需要你自己发明算法的强度。它考察的核心点是扩展欧几里得算法能否写对、中国剩余定理的本质是否理解、以及当条件之间出现矛盾时能否判断出无解。会用pow函数和逆元能解决互质情况下的CRT。但遇到模数不互质必须用两两合并的思想每一步都用扩展欧几里得来调整解。更关键的是Python的大整数运算虽然方便但如果你不清楚每一步的中间结果可能有多大写出来的代码在时间上照样会挂。这题对参加过算法训练的同学来说是稳拿分的题对只背过模板的同学来说是样例能过、提交全错的题。差距就在对扩展欧几里得返回值的处理和对合并过程的理解上。下面我用实战的视角把这套东西彻底讲透。2. 扩展欧几里得一切的底层地基2.1 从欧几里得算法到贝祖等式我们先回到最基础的地方。欧几里得算法就是辗转相除法用来求两个数的最大公约数这个大家都会写def gcd(a, b): while b: a, b b, a % b return a但扩展版要的不只是最大公约数它要求的是找到一组整数x和y使得ax by gcd(a, b)。这样的x和y一定存在这个结论叫贝祖等式是整个数论里很基础也很重要的一条性质。为什么我们非要找到这一组x和y因为中国剩余定理的整个合并过程、模逆元的求解、不互质情况下的同余变换本质上全都在用这个等式做支撑。我打一个生活化的比方。想象你在用一个天平左边只有a克和b克两种砝码右边要称出gcd(a, b)克的东西。扩展欧几里得就是在告诉你用多少个a砝码、多少个b砝码方向可以相反能刚好称出来。找不到这组配比后面的一切都无从谈起。2.2 递归实现与递推实现扩展欧几里得最常见的写法是递归。我们利用欧几里得算法的过程在递归回溯时不断调整x和y的值def exgcd(a, b): if b 0: return a, 1, 0 g, x1, y1 exgcd(b, a % b) x y1 y x1 - (a // b) * y1 return g, x, y这个递归的过程需要仔细体会一下。当递归到最底层b0时方程变成ax 0y a显然x1, y0就是一组解。然后往上一层一层回溯上一层的等式是bx1 (a%b)y1 g而我们想要的是ax by g。关键在于a % b可以写成a - (a//b)*b把这个替换进去再整理系数就能得到当前层的x和y。这个推导看起来只是代数变换但实际写代码时非常容易把符号搞错。我自己的习惯是每一层都把推导过程在草稿纸上写一遍而不是凭记忆硬背递归式子因为比赛紧张的时候记忆会骗人。如果不想用递归也可以用迭代版本。迭代版本在Python里的性能并不会比递归好太多但因为Python默认递归深度限制是1000而这题扩展欧几里得的递归深度最多是模数的位数级别所以递归写法完全够用。不过迭代版本有个好处是更容易加注释代码调试起来更直观def exgcd_iter(a, b): x0, y0, x1, y1 1, 0, 0, 1 while b: q a // b a, b b, a - q * b x0, x1 x1, x0 - q * x1 y0, y1 y1, y0 - q * y1 return a, x0, y0两种写法核心思想一致我个人的建议是把递归版本彻底练熟因为它和数学推导最贴近考场上写错了也更容易对着推导排查。2.3 在Python里最容易被忽略的负数问题这是实战中很大的一个坑。扩展欧几里得求出来的x和y完全可能是负数。比如gcd(6, 15) 3一组解是x -2, y 1因为6*(-2) 15*1 3。在数学上这完全没问题但如果你后面要用这个x去计算模逆元或者用它去构建同余方程的解那么负数必须做归一化处理。什么叫归一化就是把它调整到模数的合法范围内。x x % m在Python里%运算符对负数的结果总是非负的所以x % m可以直接把任意整数映射到[0, m-1]区间。这一点比其他很多语言舒服C里负数的取模结果可能是负的还得自己再加m调整。但舒服归舒服如果你不主动做这一步后面算出来的解可能是一个巨大的负数样例都过不了。3. 中国剩余定理从定义到实现3.1 经典CRT的适用条件标准的中国剩余定理说的是如果有一组模数m1, m2, ..., mk两两互质那么对于任意一组余数a1, a2, ..., ak这个同余方程组x ≡ a1 (mod m1)x ≡ a2 (mod m2)...x ≡ ak (mod mk)在模M m1m2...*mk的意义下有唯一解。它的求解方式是对每个模数mi令Mi M // mi然后求Mi在模mi下的逆元把所有项加起来再取模。这个过程用Python写非常短def crt(remainders, moduli): M 1 for m in moduli: M * m result 0 for a, m in zip(remainders, moduli): Mi M // m inv pow(Mi, -1, m) result (result a * Mi * inv) % M return result注意Python 3.8之后内置的pow函数支持负数次幂pow(Mi, -1, m)会直接返回模逆元。要是你用的环境版本比较老就得自己用扩展欧几里得来求逆元。比赛环境一般是新版本但如果你在自己电脑上练习建议先确认一下Python版本。这个经典模板本身不难难的是它有一个硬性前提所有模数必须两两互质。而这个前提在实际题目里几乎不会免费送给你。3.2 模数不互质才是真实战场的常态回到寻找整数这道题。题目给出的同余条件模数之间真的两两互质吗我在训练群里看到不少同学的反馈他们直接套经典CRT模板样例全过一提交就是0分或部分分。原因正是出在这里。如果模数不互质经典CRT的整个推导就失效了。因为那个M m1m2...*mk里包含了重复的质因子某些同余条件会互相打架条件一说x ≡ 2 (mod 4)条件二说x ≡ 3 (mod 6)你会发现根本不存在这样的整数因为x ≡ 2 (mod 4)说明x是偶数x ≡ 3 (mod 6)说明x是3 mod 6也就是3的倍数且是奇数这两个性质不可能同时成立。所以处理不互质模数的正确姿势是扩展中国剩余定理它的核心不是一次性求所有条件而是两两合并逐步把多个同余条件压缩成一个。3.3 合并过程的完整推导假设我们已经有了一个同余式x ≡ r1 (mod m1)现在要合并进另一个同余式x ≡ r2 (mod m2)。合并的思路是设x r1 m1 * t把它代入第二个式子r1 m1*t ≡ r2 (mod m2)移项得到m1*t ≡ r2 - r1 (mod m2)这个式子有解的前提是gcd(m1, m2)必须整除(r2 - r1)。如果不能整除整个方程组无解直接返回-1或者题目要求的无解标志。这就是为什么在代码里合并前必须先检查这一点的原因。如果有解我们就把这个式子两边同时除以g gcd(m1, m2)变成(m1/g) * t ≡ (r2 - r1)/g (mod m2/g)因为m1/g和m2/g在模m2/g意义下互质所以可以用扩展欧几里得或者pow求逆元把t解出来。然后回代得到新的合并结果新的模数m lcm(m1, m2) m1 // g * m2新的余数r (r1 m1 * t) % m这个合并过程每做一次方程组里的条件数就少一个。把所有条件合并完剩下的那个同余式就是整个方程组的通解。如果要最小正整数解就对最终模数取模再调整到正数即可。整个流程我建议你在草稿纸上至少推导一遍不要只背代码。因为为什么合并后的模数要取最小公倍数、为什么t要模m2/g这类问题一旦在赛场上卡住你只看代码是反应不过来的。4. 完整代码实现与逐行解析4.1 主流程的搭建我给出一个可以直接照着写的整体框架配合注释来说明每一步的意图。以下的实现综合了扩展欧几里得和两两合并的思路def exgcd(a, b): if b 0: return a, 1, 0 g, x1, y1 exgcd(b, a % b) x y1 y x1 - (a // b) * y1 return g, x, y def merge(r1, m1, r2, m2): # 合并两个同余条件 x ≡ r1 (mod m1) 和 x ≡ r2 (mod m2) g math.gcd(m1, m2) diff r2 - r1 if diff % g ! 0: return None # 无解 # 化简方程此时 (m1/g) 与 (m2/g) 互质 m1_g m1 // g m2_g m2 // g diff_g diff // g # 求 m1_g 在模 m2_g 下的逆元 _, inv, _ exgcd(m1_g, m2_g) inv % m2_g # 解出 t diff_g * inv (mod m2_g) t (diff_g * inv) % m2_g # 新的同余条件 m m1 // g * m2 # 最小公倍数 r (r1 m1 * t) % m return r, m def solve(remainders, moduli): r remainders[0] m moduli[0] for i in range(1, len(remainders)): res merge(r, m, remainders[i], moduli[i]) if res is None: return -1 r, m res return r % m这份代码里merge函数是整个算法的核心。它的输入是两个同余条件输出是合并后的新条件。注意这里exgcd返回的三个值中第一个是最大公约数后两个是贝祖等式的系数。我只取了inv但千万别忘了对inv取模m2_g因为扩展欧几里得直接算出来的系数可能不在合法范围内。4.2 关于求逆元的两种选择在合并过程中我们要求m1_g在模m2_g下的逆元。前面提到可以用Python内置的pow(m1_g, -1, m2_g)但这里有个值得注意的点为什么我还要特意写一个exgcd难道内置不香吗内置pow当然香但问题是它需要Python 3.8及以上版本。蓝桥杯的评测环境早就满足了所以直接pow完全没问题。我之所以在比赛代码里更倾向于自己写exgcd是因为它让我在做无解判断时更顺手。pow在模数不互质时会抛异常而exgcd直接返回最大公约数我可以顺手检查g的值。不过在实际操作中如果对exgcd的递归写法没有十足把握用pow更稳妥。节省下来的出错概率比多写几行代码更重要。我的建议是两种方案都练熟赛场上根据状态决定用哪个。4.3 大整数性能与Python特性这道题给的数据范围决定了中间结果可能相当大。Python的大整数天然支持任意精度这让我们的代码写起来毫无心理负担不像C还需要考虑溢出。但不溢出不代表不慢。两两合并时新的模数是两个模数的最小公倍数。随着合并次数增加模数会快速增长。每一次合并里都涉及一次除法和一次取模这些操作在Python里虽然慢但数据规模没到爆炸的程度就都能接受。真正要提防的是如果你没有做无解提前返回而是傻傻地合并到最后中间过程可能产生巨大无比的数字白白消耗计算时间。另外有一个细节我在代码里用了m1 // g * m2来计算最小公倍数而不是m1 * m2 // g。前者能避免中间结果先乘出一个超大数虽然Python不在乎超不超大但这是一种好的习惯在你把代码翻译成其他语言时能帮你避开64位整数溢出的坑。5. 实战经验从读题到AC的完整思路链5.1 赛场上如何快速判断考点蓝桥杯省赛的题面一般都很长像寻找整数这种题题干里会铺陈一堆故事性的描述把真正的数学条件藏在一大段文字里。这时候最重要的能力就是提取条件。我个人的读题习惯是边读边把某个数被几除余几这样的关键语句圈出来然后立刻在草稿纸上列成表格。比如题目如果给了五六个条件我列完表格后的第一反应就是这是一道同余方程组接下来立刻检查模数之间是否互质。不互质就准备走扩展中国剩余定理的路互质才敢用经典CRT。这个判断必须在读题阶段就完成而不是写完模板之后才发现样例过不去。5.2 逐一验证的调试方法写完代码后我强烈建议你先构造小数据验证再提交。比如自己随手写两个同余条件x ≡ 3 (mod 5)x ≡ 2 (mod 7)手算一遍答案应该是x ≡ 23 (mod 35)。用代码算一遍对上了再继续加条件。对于不互质的场景可以验证x ≡ 1 (mod 2)x ≡ 3 (mod 4)这两个条件显然冲突代码应该返回无解。跑通了这两个小样例再去提交心里就有底多了。实际去测的时候还有一个很实用的方式在本地用Python写一个暴力枚举的小脚本让n从1枚举到某个比较大的数把所有条件逐一验证一遍找到最小解。然后把你的CRT代码跑出来的结果和暴力结果比对。对拍是最让人放心的调试手段尤其是在比赛前期的样例测试阶段。5.3 考场上的时间分配建议蓝桥杯的Python B组省赛时间是有限的。我的建议是遇到寻找整数这类数论题如果读完题后10分钟内没有清晰思路不要死磕。先把它标记好去做后面的题等所有会的题都写完了再回过头来冷静分析。因为数论题的特征是会者不难难者不会。它不像搜索题那样可以暴力优化硬凑如果你对扩展欧几里得的原理不够熟坐在那里想半小时也想不出所以然。反过来如果你足够熟练这类题的代码量很小写起来非常快完全可以放在最后20分钟冲刺。我还想多说一个考场细节一定要把输入数据的范围看清楚。有些同余条件的余数可能非常大甚至余数都不一定小于模数。你以为它给的余数肯定小于模数直接拿过去用结果合并时就出现负数导致diff % g的判断出错。如果输入的余数不保证小于模数一定要自己在代码入口统一做一次归一化r r % m。6. 常见问题与排查技巧6.1 典型错误对照表我把这题最常见的错误整理成一张表方便你对照排查症状可能原因修复方式样例能过、提交全错误用经典CRT模数不互质改为两两合并的扩展CRT结果一直是负数扩展欧几里得求出的系数未取模对inv和t做%归一化无解判断失效未检查diff % g是否为零合并前必须做整除判断大样例运行超时合并次数过多或数据读取太慢用sys.stdin.read一次性读入答案偏大未对最终结果取模返回前对最终模数取模并调整为正数6.2 无解条件的深入理解很多同学知道要检查diff % g但不知道为什么。我再用合并推导里的那个式子解释一下m1*t ≡ r2 - r1 (mod m2)这个方程有解的充要条件是gcd(m1, m2)整除r2 - r1。为什么因为等式两边除以g之后左边变成(m1/g)*t右边变成(r2-r1)/g而m2/g是整数。如果(r2-r1)不是g的倍数这个分数根本就不是整数整个同余式就无从谈起。这个道理类似日常生活中的分糖果场景你有若干个袋子每袋糖果数固定要求每个孩子拿到的总数满足某种余数关系。只有当可分配总数和孩子总数满足整除条件时分配方案才可能存在。理解了这层直觉考试时即使推导公式忘了也能靠直觉判断该不该输出无解。6.3 我踩过的坑最后分享几个我实际踩过的坑。第一个坑是Python的递归深度。扩展欧几里得本身递归深度只有几十层问题不大但如果你把合并过程也写成递归就可能出问题。我的建议是合并循环用for循环不要递归只有exgcd本身用递归其他的交给循环处理。第二个坑是输入解析。蓝桥杯的输入格式有时候很坑空行、多余空格都可能出现。我习惯用sys.stdin.read().split()一次性把所有数字拿到避免一行行读的时候被格式问题干扰。这个习惯在时间紧张的时候特别有用。第三个坑是结果要对最初的最小正整数负责。如果你合并到最后得到的r是一个负数直接输出就错了。必须做一次r % m然后如果是0还要注意题目要求的是正整数解那就要输出m而不是0。这个细节在答案恰好是模数整数倍时会出现。很多同学在这一点上翻车我印象很深。7. 一些解题之外的体会练这道题给我最大的感受不是说多背一个模板而是真正理解了中国剩余定理这个名字背后的两块拼图一是模数的互质性决定了用哪种方法二是扩展欧几里得并不是单独存在的工具它几乎嵌在所有同余方程的角落里。如果你正在备战蓝桥杯省赛我的建议是把扩展欧几里得的推导过程自己独立推三遍以上直到你能在没有任何参考的情况下从贝祖等式一路写到递归代码。这个过程花的时间不多但在考场上给你带来的底气是背模板完全给不了的。另外寻找整数这类题的变体很多。有的题会把模数的数量给到十万级别要求你用线性的合并顺序处理有的题会反过来问你某个区间内有多少个解还有的题把同余条件藏在地图坐标或者字符串哈希的碰撞检测里。原理都是同一个只是表现形式不同。最后再分享一个小技巧本地练习的时候不妨把这道题的暴力枚举版本也写出来用随机数据去对拍。随机生成几十组小范围的数据跑一遍暴力再跑一遍扩展CRT逐一比对结果。这个习惯能帮你提前发现很多你以为写对了、实际上边界条件有问题的Bug。等到赛场上你对这套代码的信心会完全不一样。 
长河君 · 2026/10/21 12:42:39 · 阅读 1.2k 蓝桥杯“寻找整数”题解：扩展欧几里得与不互质模数的中国剩余定理
1. 题目拆解与考点定位1.1 这道题到底在问什么寻找整数这道题从标题上的算法标签就能看出它的真实身份数论里的同余方程求解问题而且点名了扩展欧几里得和中国剩余定理两个关键工具。但我先泼一盆冷水如果你以为这只是套一个中国剩余定理模板就能过的题那大概率会在赛场上翻车。蓝桥杯的省赛题尤其到了Python B组的中后段题位很少会直接给你一份模数两两互质、直接套CRT的裸题。它既然加上了普及的难度标签就一定在经典模型之外埋了需要你自己发现的细节。这类题的核心叙述逻辑通常是这样的给定若干组形如某个数除以a余b的条件让你求满足所有条件的最小正整数或者某个范围内的解。看起来像是小学奥数里韩信点兵的升级版但实际上它真正考察的是你能否在考场上快速识别出这是一个线性同余方程组并且知道在模数不互质时不能无脑使用标准中国剩余定理。1.2 为什么它值得专门写一篇省赛Python组的题难度定级为普及其实非常微妙。它比纯入门模板题多了一层思考但又没有到省选那种需要你自己发明算法的强度。它考察的核心点是扩展欧几里得算法能否写对、中国剩余定理的本质是否理解、以及当条件之间出现矛盾时能否判断出无解。会用pow函数和逆元能解决互质情况下的CRT。但遇到模数不互质必须用两两合并的思想每一步都用扩展欧几里得来调整解。更关键的是Python的大整数运算虽然方便但如果你不清楚每一步的中间结果可能有多大写出来的代码在时间上照样会挂。这题对参加过算法训练的同学来说是稳拿分的题对只背过模板的同学来说是样例能过、提交全错的题。差距就在对扩展欧几里得返回值的处理和对合并过程的理解上。下面我用实战的视角把这套东西彻底讲透。2. 扩展欧几里得一切的底层地基2.1 从欧几里得算法到贝祖等式我们先回到最基础的地方。欧几里得算法就是辗转相除法用来求两个数的最大公约数这个大家都会写def gcd(a, b): while b: a, b b, a % b return a但扩展版要的不只是最大公约数它要求的是找到一组整数x和y使得ax by gcd(a, b)。这样的x和y一定存在这个结论叫贝祖等式是整个数论里很基础也很重要的一条性质。为什么我们非要找到这一组x和y因为中国剩余定理的整个合并过程、模逆元的求解、不互质情况下的同余变换本质上全都在用这个等式做支撑。我打一个生活化的比方。想象你在用一个天平左边只有a克和b克两种砝码右边要称出gcd(a, b)克的东西。扩展欧几里得就是在告诉你用多少个a砝码、多少个b砝码方向可以相反能刚好称出来。找不到这组配比后面的一切都无从谈起。2.2 递归实现与递推实现扩展欧几里得最常见的写法是递归。我们利用欧几里得算法的过程在递归回溯时不断调整x和y的值def exgcd(a, b): if b 0: return a, 1, 0 g, x1, y1 exgcd(b, a % b) x y1 y x1 - (a // b) * y1 return g, x, y这个递归的过程需要仔细体会一下。当递归到最底层b0时方程变成ax 0y a显然x1, y0就是一组解。然后往上一层一层回溯上一层的等式是bx1 (a%b)y1 g而我们想要的是ax by g。关键在于a % b可以写成a - (a//b)*b把这个替换进去再整理系数就能得到当前层的x和y。这个推导看起来只是代数变换但实际写代码时非常容易把符号搞错。我自己的习惯是每一层都把推导过程在草稿纸上写一遍而不是凭记忆硬背递归式子因为比赛紧张的时候记忆会骗人。如果不想用递归也可以用迭代版本。迭代版本在Python里的性能并不会比递归好太多但因为Python默认递归深度限制是1000而这题扩展欧几里得的递归深度最多是模数的位数级别所以递归写法完全够用。不过迭代版本有个好处是更容易加注释代码调试起来更直观def exgcd_iter(a, b): x0, y0, x1, y1 1, 0, 0, 1 while b: q a // b a, b b, a - q * b x0, x1 x1, x0 - q * x1 y0, y1 y1, y0 - q * y1 return a, x0, y0两种写法核心思想一致我个人的建议是把递归版本彻底练熟因为它和数学推导最贴近考场上写错了也更容易对着推导排查。2.3 在Python里最容易被忽略的负数问题这是实战中很大的一个坑。扩展欧几里得求出来的x和y完全可能是负数。比如gcd(6, 15) 3一组解是x -2, y 1因为6*(-2) 15*1 3。在数学上这完全没问题但如果你后面要用这个x去计算模逆元或者用它去构建同余方程的解那么负数必须做归一化处理。什么叫归一化就是把它调整到模数的合法范围内。x x % m在Python里%运算符对负数的结果总是非负的所以x % m可以直接把任意整数映射到[0, m-1]区间。这一点比其他很多语言舒服C里负数的取模结果可能是负的还得自己再加m调整。但舒服归舒服如果你不主动做这一步后面算出来的解可能是一个巨大的负数样例都过不了。3. 中国剩余定理从定义到实现3.1 经典CRT的适用条件标准的中国剩余定理说的是如果有一组模数m1, m2, ..., mk两两互质那么对于任意一组余数a1, a2, ..., ak这个同余方程组x ≡ a1 (mod m1)x ≡ a2 (mod m2)...x ≡ ak (mod mk)在模M m1m2...*mk的意义下有唯一解。它的求解方式是对每个模数mi令Mi M // mi然后求Mi在模mi下的逆元把所有项加起来再取模。这个过程用Python写非常短def crt(remainders, moduli): M 1 for m in moduli: M * m result 0 for a, m in zip(remainders, moduli): Mi M // m inv pow(Mi, -1, m) result (result a * Mi * inv) % M return result注意Python 3.8之后内置的pow函数支持负数次幂pow(Mi, -1, m)会直接返回模逆元。要是你用的环境版本比较老就得自己用扩展欧几里得来求逆元。比赛环境一般是新版本但如果你在自己电脑上练习建议先确认一下Python版本。这个经典模板本身不难难的是它有一个硬性前提所有模数必须两两互质。而这个前提在实际题目里几乎不会免费送给你。3.2 模数不互质才是真实战场的常态回到寻找整数这道题。题目给出的同余条件模数之间真的两两互质吗我在训练群里看到不少同学的反馈他们直接套经典CRT模板样例全过一提交就是0分或部分分。原因正是出在这里。如果模数不互质经典CRT的整个推导就失效了。因为那个M m1m2...*mk里包含了重复的质因子某些同余条件会互相打架条件一说x ≡ 2 (mod 4)条件二说x ≡ 3 (mod 6)你会发现根本不存在这样的整数因为x ≡ 2 (mod 4)说明x是偶数x ≡ 3 (mod 6)说明x是3 mod 6也就是3的倍数且是奇数这两个性质不可能同时成立。所以处理不互质模数的正确姿势是扩展中国剩余定理它的核心不是一次性求所有条件而是两两合并逐步把多个同余条件压缩成一个。3.3 合并过程的完整推导假设我们已经有了一个同余式x ≡ r1 (mod m1)现在要合并进另一个同余式x ≡ r2 (mod m2)。合并的思路是设x r1 m1 * t把它代入第二个式子r1 m1*t ≡ r2 (mod m2)移项得到m1*t ≡ r2 - r1 (mod m2)这个式子有解的前提是gcd(m1, m2)必须整除(r2 - r1)。如果不能整除整个方程组无解直接返回-1或者题目要求的无解标志。这就是为什么在代码里合并前必须先检查这一点的原因。如果有解我们就把这个式子两边同时除以g gcd(m1, m2)变成(m1/g) * t ≡ (r2 - r1)/g (mod m2/g)因为m1/g和m2/g在模m2/g意义下互质所以可以用扩展欧几里得或者pow求逆元把t解出来。然后回代得到新的合并结果新的模数m lcm(m1, m2) m1 // g * m2新的余数r (r1 m1 * t) % m这个合并过程每做一次方程组里的条件数就少一个。把所有条件合并完剩下的那个同余式就是整个方程组的通解。如果要最小正整数解就对最终模数取模再调整到正数即可。整个流程我建议你在草稿纸上至少推导一遍不要只背代码。因为为什么合并后的模数要取最小公倍数、为什么t要模m2/g这类问题一旦在赛场上卡住你只看代码是反应不过来的。4. 完整代码实现与逐行解析4.1 主流程的搭建我给出一个可以直接照着写的整体框架配合注释来说明每一步的意图。以下的实现综合了扩展欧几里得和两两合并的思路def exgcd(a, b): if b 0: return a, 1, 0 g, x1, y1 exgcd(b, a % b) x y1 y x1 - (a // b) * y1 return g, x, y def merge(r1, m1, r2, m2): # 合并两个同余条件 x ≡ r1 (mod m1) 和 x ≡ r2 (mod m2) g math.gcd(m1, m2) diff r2 - r1 if diff % g ! 0: return None # 无解 # 化简方程此时 (m1/g) 与 (m2/g) 互质 m1_g m1 // g m2_g m2 // g diff_g diff // g # 求 m1_g 在模 m2_g 下的逆元 _, inv, _ exgcd(m1_g, m2_g) inv % m2_g # 解出 t diff_g * inv (mod m2_g) t (diff_g * inv) % m2_g # 新的同余条件 m m1 // g * m2 # 最小公倍数 r (r1 m1 * t) % m return r, m def solve(remainders, moduli): r remainders[0] m moduli[0] for i in range(1, len(remainders)): res merge(r, m, remainders[i], moduli[i]) if res is None: return -1 r, m res return r % m这份代码里merge函数是整个算法的核心。它的输入是两个同余条件输出是合并后的新条件。注意这里exgcd返回的三个值中第一个是最大公约数后两个是贝祖等式的系数。我只取了inv但千万别忘了对inv取模m2_g因为扩展欧几里得直接算出来的系数可能不在合法范围内。4.2 关于求逆元的两种选择在合并过程中我们要求m1_g在模m2_g下的逆元。前面提到可以用Python内置的pow(m1_g, -1, m2_g)但这里有个值得注意的点为什么我还要特意写一个exgcd难道内置不香吗内置pow当然香但问题是它需要Python 3.8及以上版本。蓝桥杯的评测环境早就满足了所以直接pow完全没问题。我之所以在比赛代码里更倾向于自己写exgcd是因为它让我在做无解判断时更顺手。pow在模数不互质时会抛异常而exgcd直接返回最大公约数我可以顺手检查g的值。不过在实际操作中如果对exgcd的递归写法没有十足把握用pow更稳妥。节省下来的出错概率比多写几行代码更重要。我的建议是两种方案都练熟赛场上根据状态决定用哪个。4.3 大整数性能与Python特性这道题给的数据范围决定了中间结果可能相当大。Python的大整数天然支持任意精度这让我们的代码写起来毫无心理负担不像C还需要考虑溢出。但不溢出不代表不慢。两两合并时新的模数是两个模数的最小公倍数。随着合并次数增加模数会快速增长。每一次合并里都涉及一次除法和一次取模这些操作在Python里虽然慢但数据规模没到爆炸的程度就都能接受。真正要提防的是如果你没有做无解提前返回而是傻傻地合并到最后中间过程可能产生巨大无比的数字白白消耗计算时间。另外有一个细节我在代码里用了m1 // g * m2来计算最小公倍数而不是m1 * m2 // g。前者能避免中间结果先乘出一个超大数虽然Python不在乎超不超大但这是一种好的习惯在你把代码翻译成其他语言时能帮你避开64位整数溢出的坑。5. 实战经验从读题到AC的完整思路链5.1 赛场上如何快速判断考点蓝桥杯省赛的题面一般都很长像寻找整数这种题题干里会铺陈一堆故事性的描述把真正的数学条件藏在一大段文字里。这时候最重要的能力就是提取条件。我个人的读题习惯是边读边把某个数被几除余几这样的关键语句圈出来然后立刻在草稿纸上列成表格。比如题目如果给了五六个条件我列完表格后的第一反应就是这是一道同余方程组接下来立刻检查模数之间是否互质。不互质就准备走扩展中国剩余定理的路互质才敢用经典CRT。这个判断必须在读题阶段就完成而不是写完模板之后才发现样例过不去。5.2 逐一验证的调试方法写完代码后我强烈建议你先构造小数据验证再提交。比如自己随手写两个同余条件x ≡ 3 (mod 5)x ≡ 2 (mod 7)手算一遍答案应该是x ≡ 23 (mod 35)。用代码算一遍对上了再继续加条件。对于不互质的场景可以验证x ≡ 1 (mod 2)x ≡ 3 (mod 4)这两个条件显然冲突代码应该返回无解。跑通了这两个小样例再去提交心里就有底多了。实际去测的时候还有一个很实用的方式在本地用Python写一个暴力枚举的小脚本让n从1枚举到某个比较大的数把所有条件逐一验证一遍找到最小解。然后把你的CRT代码跑出来的结果和暴力结果比对。对拍是最让人放心的调试手段尤其是在比赛前期的样例测试阶段。5.3 考场上的时间分配建议蓝桥杯的Python B组省赛时间是有限的。我的建议是遇到寻找整数这类数论题如果读完题后10分钟内没有清晰思路不要死磕。先把它标记好去做后面的题等所有会的题都写完了再回过头来冷静分析。因为数论题的特征是会者不难难者不会。它不像搜索题那样可以暴力优化硬凑如果你对扩展欧几里得的原理不够熟坐在那里想半小时也想不出所以然。反过来如果你足够熟练这类题的代码量很小写起来非常快完全可以放在最后20分钟冲刺。我还想多说一个考场细节一定要把输入数据的范围看清楚。有些同余条件的余数可能非常大甚至余数都不一定小于模数。你以为它给的余数肯定小于模数直接拿过去用结果合并时就出现负数导致diff % g的判断出错。如果输入的余数不保证小于模数一定要自己在代码入口统一做一次归一化r r % m。6. 常见问题与排查技巧6.1 典型错误对照表我把这题最常见的错误整理成一张表方便你对照排查症状可能原因修复方式样例能过、提交全错误用经典CRT模数不互质改为两两合并的扩展CRT结果一直是负数扩展欧几里得求出的系数未取模对inv和t做%归一化无解判断失效未检查diff % g是否为零合并前必须做整除判断大样例运行超时合并次数过多或数据读取太慢用sys.stdin.read一次性读入答案偏大未对最终结果取模返回前对最终模数取模并调整为正数6.2 无解条件的深入理解很多同学知道要检查diff % g但不知道为什么。我再用合并推导里的那个式子解释一下m1*t ≡ r2 - r1 (mod m2)这个方程有解的充要条件是gcd(m1, m2)整除r2 - r1。为什么因为等式两边除以g之后左边变成(m1/g)*t右边变成(r2-r1)/g而m2/g是整数。如果(r2-r1)不是g的倍数这个分数根本就不是整数整个同余式就无从谈起。这个道理类似日常生活中的分糖果场景你有若干个袋子每袋糖果数固定要求每个孩子拿到的总数满足某种余数关系。只有当可分配总数和孩子总数满足整除条件时分配方案才可能存在。理解了这层直觉考试时即使推导公式忘了也能靠直觉判断该不该输出无解。6.3 我踩过的坑最后分享几个我实际踩过的坑。第一个坑是Python的递归深度。扩展欧几里得本身递归深度只有几十层问题不大但如果你把合并过程也写成递归就可能出问题。我的建议是合并循环用for循环不要递归只有exgcd本身用递归其他的交给循环处理。第二个坑是输入解析。蓝桥杯的输入格式有时候很坑空行、多余空格都可能出现。我习惯用sys.stdin.read().split()一次性把所有数字拿到避免一行行读的时候被格式问题干扰。这个习惯在时间紧张的时候特别有用。第三个坑是结果要对最初的最小正整数负责。如果你合并到最后得到的r是一个负数直接输出就错了。必须做一次r % m然后如果是0还要注意题目要求的是正整数解那就要输出m而不是0。这个细节在答案恰好是模数整数倍时会出现。很多同学在这一点上翻车我印象很深。7. 一些解题之外的体会练这道题给我最大的感受不是说多背一个模板而是真正理解了中国剩余定理这个名字背后的两块拼图一是模数的互质性决定了用哪种方法二是扩展欧几里得并不是单独存在的工具它几乎嵌在所有同余方程的角落里。如果你正在备战蓝桥杯省赛我的建议是把扩展欧几里得的推导过程自己独立推三遍以上直到你能在没有任何参考的情况下从贝祖等式一路写到递归代码。这个过程花的时间不多但在考场上给你带来的底气是背模板完全给不了的。另外寻找整数这类题的变体很多。有的题会把模数的数量给到十万级别要求你用线性的合并顺序处理有的题会反过来问你某个区间内有多少个解还有的题把同余条件藏在地图坐标或者字符串哈希的碰撞检测里。原理都是同一个只是表现形式不同。最后再分享一个小技巧本地练习的时候不妨把这道题的暴力枚举版本也写出来用随机数据去对拍。随机生成几十组小范围的数据跑一遍暴力再跑一遍扩展CRT逐一比对结果。这个习惯能帮你提前发现很多你以为写对了、实际上边界条件有问题的Bug。等到赛场上你对这套代码的信心会完全不一样。