企业官网建设流程全解析

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

这个递归的过程需要仔细体会一下。当递归到最底层b=0时，方程变成ax + 0y = a，显然x=1, y=0就是一组解。然后往上一层一层回溯：上一层的等式是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 典型错误对照表

我把这题最常见的错误整理成一张表，方便你对照排查：

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。等到赛场上，你对这套代码的信心会完全不一样。