企业官网建设流程全解析

这道题我刷的时候印象特别深，主要原因是它看起来实在不像数论题。标题就叫“寻找整数”，读完题面才发现，真正的任务是解一组同余方程：给出若干条形如x mod p_i = r_i的条件，让你求满足全部条件的最小正整数。难度标签是“普及+”。我当时第一反应是“直接枚举不就行了”，结果一看模数的数量级，立刻意识到暴力枚举连跑都跑不完，最小解可能是一个天文数字。这篇文章就把这道题背后的扩展欧几里得、中国剩余定理和扩展中国剩余定理完整拆一遍，适合正在备赛蓝桥杯、或者刚开始啃数论模块的选手。看完之后，你不仅能直接套用模板，还能说清楚每一步到底在算什么。

1. 先说说这道题为什么坑在“寻找”二字

“寻找整数”这个名字起得很容易误导人，我第一次看到时以为是一道脑筋急转弯或者模拟题。拿到题面之后才明白，它是典型的同余方程组问题。题目输入可以理解为：给定n条同余式，每行两个整数p_i和r_i，表示

x ≡ r_i (mod p_i)

要求输出满足全部条件的最小正整数x。

这类题目的数据范围决定了解法。假设模数只有几个小数字，比如同时满足x mod 3 = 2、x mod 5 = 3、x mod 7 = 2，手算都能出来，暴力枚举从 1 开始检查也非常快。但普及+以上难度的题不会让你这么舒服，模数的乘积（最小公倍数）可能直接超过10^18，甚至 Python 的大整数都要转好几圈。这时如果还在枚举，时间复杂度是不可接受的，必须用数论方法直接构造出解。

1.1 题目给我的第一印象：暴力不是选项

先别急着写代码，用最朴素的思路分析一下暴力为什么不可行。

假设读入了 20 个同余方程，每个模数都是一位或两位数的量级。看起来枚举范围不会太大，但问题在于“最小正整数解”可能是所有模数的最小公倍数级别。比如只给两条方程：

x ≡ 0 (mod 999999937)

x ≡ 0 (mod 999999929)

这两个模数都是素数而且互质，最小公倍数接近10^18，从 1 开始枚举要枚举到10^18才能命中第一个公共解。哪怕每秒跑一亿次循环，也要跑三百多年。

即使换一个方向，从最大的模数开始枚举，步长取最大模数，效率依然不稳定。因为多个模数之间可能存在公因数，真正的周期是所有模数的最小公倍数，而不是其中某一个模数。所以“寻找整数”的关键不在于顺序找，而在于如何把若干个同余条件压缩成一个更小的搜索空间。

1.2 从简单的例子感受同余方程组

为了后面便于对照代码，我先把一个简单例子放在这里。假设题面输入是：

3 3 2 5 3 7 2

三条条件分别是：

• x ≡ 2 (mod 3)
• x ≡ 3 (mod 5)
• x ≡ 2 (mod 7)

这个例子的最小正整数解是23。为什么是 23？因为三个模数两两互质，解可以写成模3 * 5 * 7 = 105的一个剩余类，最小正整数解落在[1, 105]之间。手动验证一下：23 mod 3 = 2，23 mod 5 = 3，23 mod 7 = 2，全部命中。

这个例子比较简单，但它足以说明：真正的难点不是“能否枚举到答案”，而是“如何跳过大量无效数字直接定位答案”。

2. 中国剩余定理的适用边界：模数互质才敢用

遇到同余方程组，很多学过数论的选手第一反应就是中国剩余定理（CRT）。它确实是一个非常优美的构造，但需要注意它的适用前提：所有模数必须两两互质。

2.1 CRT 的经典构造逻辑

假设有n个方程，模数分别是m_1, m_2, ..., m_n，且任意两个模数互质。记

M = m_1 * m_2 * ... * m_n

然后对第i个方程定义

M_i = M / m_i

因为模数两两互质，所以M_i和m_i的公约数只有 1，也就是说M_i在模m_i下存在逆元。设这个逆元为t_i，满足

M_i * t_i ≡ 1 (mod m_i)

于是可以构造

x = Σ (r_i * M_i * t_i) mod M

这个构造的精妙之处在于：对于第i个方程，M_i中包含除m_i以外的所有模数因子，所以M_i被其他模数整除，对其他方程的贡献全是 0；而它对自己那个方程贡献恰好是r_i。一个式子同时满足所有同余条件。

用生活中的例子打比方：三盏不同周期的灯，按各自的节奏闪动，CRT 就是找到一个时刻，让三盏灯同时处于指定状态。只要周期之间没有公共节拍，这个时刻必然存在，而且每隔一个“大周期”重复一次。

2.2 不互质时 CRT 为什么立刻失效

现在关键问题来了：蓝桥杯这道题里的模数并不是都互质的。如果直接套 CRT，麻烦立刻出现。

比如方程组：

• x ≡ 0 (mod 2)
• x ≡ 0 (mod 4)

这个方程组显然有解，x = 4就满足条件。但M = 8，M_1 = 4，M_2 = 2。注意4和2都不是互质的，所以M_1在模 2 下没有逆元，M_2在模 4 下也没有逆元。CRT 构造公式成立的前提直接崩了，公式没法计算。

更夸张的情况是，模数之间存在公因数时，CRT 的构造式虽然可能凑出某个数，但那并不等于真正的最小解。因此，处理不互质模数，必须放弃一次性构造，改成“逐对合并”的思路。这个思路就是扩展中国剩余定理（EXCRT），很多资料里也叫扩展 CRT。

2.3 逐对合并的核心思路

EXCRT 的思想很直白：先从前两个方程开始，把它们合并成一个等价的同余方程，再和第三个方程合并，如此反复。合并的本质是求解二元一次不定方程。

假设现在有两个方程：

x ≡ r_1 (mod m_1)

x ≡ r_2 (mod m_2)

第一个方程的所有解可以写成

x = r_1 + m_1 * k

代入第二个方程：

r_1 + m_1 * k ≡ r_2 (mod m_2)

整理一下：

m_1 * k ≡ r_2 - r_1 (mod m_2)

这就是一个典型的“一元线性同余方程”。解出k后，代回去就得到一个新的同余方程，新的模数是m_1和m_2的最小公倍数，新的余数就是求出来的这个x对最小公倍数取模。

这个过程如果用大白话说：把两个“周期性条件”合成一个新的“合成周期条件”。合成后的周期是两个原周期的公共周期，合成后的相位则同时满足两个原始相位。

3. 扩展欧几里得：合并方程时真正在做的数学操作

上一节的核心等式是m_1 * k ≡ r_2 - r_1 (mod m_2)，现在需要真正把它求出来。这里的工具就是扩展欧几里得算法（exgcd）。

3.1 递归式 exgcd 是怎么推出来的

扩展欧几里得算法解决的问题是：对于任意整数a和b，找到一组整数x和y，使得

a*x + b*y = gcd(a, b)

普通的欧几里得算法只会算最大公约数，扩展版本额外返回一组系数。递归推导并不复杂：

当b = 0时，gcd(a, 0) = a，显然取x = 1, y = 0即可。

当b ≠ 0时，递归调用exgcd(b, a % b)，假设得到一组解x0, y0，满足：

b*x0 + (a % b)*y0 = gcd(b, a % b)

注意gcd(a, b) == gcd(b, a % b)，而a % b = a - (a // b) * b，所以有：

b*x0 + (a - (a // b) * b) * y0 = a*y0 + b*(x0 - (a // b)*y0)

于是原方程的一组解就是：

x = y0

y = x0 - (a // b) * y0

Python 写出来很短：

def exgcd(a, b): if b == 0: return 1, 0, a x0, y0, g = exgcd(b, a % b) return y0, x0 - (a // b) * y0, g

为什么这个函数在 EXCRT 里必不可少？因为它能做两件事：判断线性同余方程是否有解，以及求出乘法逆元。

3.2 用 exgcd 解一元线性同余方程

一元线性同余方程的标准形式是：

a * t ≡ c (mod m)

把它改写成等式：

a * t + m * s = c

令g = gcd(a, m)。因为等式左边一定是g的倍数，所以如果c不能被g整除，方程无解。这一步非常关键，它对应 EXCRT 合并时的无解判断。

如果c % g == 0，把等式两边同时除以g：

(a/g) * t + (m/g) * s = c/g

此时a/g和m/g互质，求a/g在模m/g下的逆元，就能得到t。整个过程就是“约去公共因子 + 求逆元 + 还原余数”。

举个例子，解方程：

6 * t ≡ 2 (mod 8)

gcd(6, 8) = 2，右边2能被2整除，有解。两边除 2 得：

3 * t ≡ 1 (mod 4)

3在模4下的逆元是3，因为3*3 = 9 ≡ 1 (mod 4)，于是t ≡ 3 (mod 4)。验证一下：6 * 3 = 18，18 mod 8 = 2，成立。

3.3 合并公式里的三个符号为什么都除以 g

回到两个方程的合并：

m_1 * k ≡ r_2 - r_1 (mod m_2)

如果直接对两边求逆元，前提是gcd(m_1, m_2) = 1。如果不互质，必须先除公约数。设：

g = gcd(m_1, m_2)

那么只有当(r_2 - r_1) % g == 0时才有解。这一步对应到实际题目里就是：输入给出的若干同余条件可能自相矛盾，比如x ≡ 1 (mod 2)和x ≡ 0 (mod 4)永远不可能同时成立，合并到这一步就会判出无解。

在有解的前提下，同余方程变为：

(m_1/g) * k ≡ (r_2 - r_1)/g (mod m_2/g)

此时左边系数和模数互质，可以安全求逆元。新的周期变成：

new_M = lcm(m_1, m_2) = m_1 // g * m_2

这里写m_1 // g * m_2而不是m_1 * m_2 // g是为了防止中间结果溢出，在 C++ 里这是必须注意的；Python 虽然不会真的溢出，但养成先除后乘的习惯没有坏处。

最后新的余数：

new_R = (r_1 + m_1 * k) % new_M

这样得到的(new_R, new_M)和原来的两个方程在解集上完全等价，只是把所有解压缩到了一个更小的周期里。

4. Python 版 EXCRT 完整实现与逐行拆解

理论部分讲完，直接上代码。这个模板适合在蓝桥杯等比赛里直接背下来用，下面我会逐段解释每一行的作用。

4.1 主函数骨架

import sys import math def exgcd(a, b): """返回 (x, y, g)，满足 a*x + b*y = g = gcd(a,b)""" if b == 0: return 1, 0, a x0, y0, g = exgcd(b, a % b) return y0, x0 - (a // b) * y0, g def inv_mod(a, m): """求 a 在模 m 下的逆元，要求 gcd(a, m) = 1""" x, y, g = exgcd(a % m, m) if g != 1: return None return x % m def merge(r1, m1, r2, m2): """ 已知 x ≡ r1 (mod m1) x ≡ r2 (mod m2) 返回合并后的 (r, m)，如果无解返回 None """ a = m1 % m2 c = (r2 - r1) % m2 g = math.gcd(a, m2) if c % g != 0: return None a1 = a // g c1 = c // g m1_new = m2 // g k = inv_mod(a1 % m1_new, m1_new) if k is None: return None k = k * c1 % m1_new new_m = m1 // g * m2 new_r = (r1 + m1 * k) % new_m return new_r, new_m def solve(): input = sys.stdin.readline n = int(input()) r = 0 m = 1 for _ in range(n): p, r_i = map(int, input().split()) r_i %= p merged = merge(r, m, r_i, p) if merged is None: print("无解") return r, m = merged ans = r % m if ans == 0: ans = m print(ans) if __name__ == "__main__": solve()

很多资料里把合并过程直接写进主循环，我觉得拆成独立函数更清晰。主循环做三件事：读入一条方程、和当前结果合并、更新当前结果。初始时r = 0, m = 1，表示x ≡ 0 (mod 1)，这是恒真式，不影响后面的合并。

4.2 两个容易写错的地方

第一个坑：求逆元之前一定要a % m取正。exgcd返回的x可能是负数，x % m能确保结果落在[0, m)。如果输入数据中m1比m2大，a = m1 % m2这一步就会自动变小；如果不取模，逆元可能根本不存在，或者后续计算出现奇怪的负数。

第二个坑：r_i %= p这句不能省。题目如果保证r_i < p可以省略，但有些数据不会严格保证，比如输入5 8表示x ≡ 8 (mod 5)，实际上等价于x ≡ 3 (mod 5)。不先取模，合并时的c = (r2 - r1) % m2虽然也能通过取模修正，但容易让c变成一个很大的负数，增加出错概率。读入时直接处理掉，逻辑最干净。

4.3 用前文的例子验证代码

拿 1.2 里的例子跑一遍：

3 3 2 5 3 7 2

• 初始：r = 0, m = 1
• 合并x ≡ 0 (mod 1)和x ≡ 2 (mod 3)，得到r = 2, m = 3
• 合并x ≡ 2 (mod 3)和x ≡ 3 (mod 5)，得到r = 8, m = 15
• 合并x ≡ 8 (mod 15)和x ≡ 2 (mod 7)，得到r = 23, m = 105

输出23，完全正确。再看一个模数不互质的例子：

2 6 4 8 6

合并步骤：

• 当前r = 0, m = 1
• 合并x ≡ 0 (mod 1)和x ≡ 4 (mod 6)，得到r = 4, m = 6
• 合并x ≡ 4 (mod 6)和x ≡ 6 (mod 8)
  • a = 6 % 8 = 6
  • c = (6 - 4) % 8 = 2
  • g = gcd(6, 8) = 2
  • c % g = 0，有解
  • a1 = 3，c1 = 1，m1_new = 4
  • 3在模4下的逆元是3
  • k = 3 * 1 % 4 = 3
  • new_m = 6 // 2 * 8 = 24
  • new_r = (4 + 6 * 3) % 24 = 22

输出22。检查一下：22 mod 6 = 4，22 mod 8 = 6，成立。

5. 实测性能、几个隐藏细节和考场上该怎么打

模板能用只是第一步，真正比赛的时候还有不少细节值得单独拎出来说。

5.1 在蓝桥杯环境下的实测表现

我在本地针对类似规模的数据做过压力测试：n = 100，每个模数在10^9左右随机选取，最小解可能达到10^18量级。用上面的 Python 实现跑一遍，总耗时基本在几十毫秒到一两百毫秒之间，怎么跑都不会超时。

原因在于复杂度分析：每合并一条方程，需要一次gcd和一次exgcd，两者都是O(log m)级别。合并n条方程的总复杂度是O(n log M)，M是所有模数的最小公倍数。即使M达到10^18，log也只有几十层，这个开销在竞赛限时内完全可以忽略。

Python 在这个题上的优势是大整数原生支持，10^18甚至更大的数字都不需要额外处理。如果用 C++ 手写高精度反而麻烦。

5.2 无解、边界值和数据范围

题目如果构造了矛盾条件，合并函数会返回None。比如给两条方程：

• x ≡ 1 (mod 2)
• x ≡ 0 (mod 4)

合并时a = 2 % 4 = 2，c = (0 - 1) % 4 = 3，g = 2，c % g = 1，不等于 0，直接判定无解。实际含义也很直观：一个数同时是偶数（模 2 余 0）又要模 2 余 1，永远不可能。

另外，输出边界要注意。代码最后：

ans = r % m if ans == 0: ans = m print(ans)

如果求出来的r恰好是 0，比如方程组整体解集是x ≡ 0 (mod 105)，那么最小正整数解应该是 105，而不是 0。有些题目要求输出非负整数，那就直接输出 0；但大部分“寻找整数”类题目要求正整数，必须做这个判断。

数据范围还有一个隐含问题：合并过程中new_m = m1 // g * m2可能会非常大，Python 不会崩，但要注意输出格式，有些题目要求对某个大数取模输出，这时需要在最后对要求的模数再取一次模。蓝桥杯这题一般不涉及，因为要求的是绝对最小解，但在其他OJ题里很容易遇到。

5.3 模板该怎么背

我不建议死记完整代码，记忆链可以拆成三块：

第一块是exgcd，递归式很短，理解推导过程后不容易忘。关键点就是a % b = a - (a // b) * b这个展开式。

第二块是inv_mod，它建立在这个等式上：a*x + m*y = 1，那么x就是逆元。只要gcd(a, m) == 1，必有解。注意返回时要取模转正。

第三块是merge，记忆模板如下：

1. 把m1 * k ≡ r2 - r1 (mod m2)写成a = m1 % m2，c = (r2 - r1) % m2
2. 求g = gcd(a, m2)
3. 无解判断：c % g != 0
4. 约分后求逆元得到k
5. 更新m = lcm，更新r = (r1 + m1 * k) % m

三步模板扣下来，比背整段代码可靠得多。考场上一旦紧张导致记混，直接按“解线性同余方程 → 求逆元 → 更新周期”这个逻辑链一步一步推，也能现场写对。

我在实际写这个模板时还踩过一个小坑：合并时求a1 % m1_new的逆元，如果直接传a1而没取模，在极少数情况下会因为符号问题导致exgcd内部递归出现负数输入，虽然结果可能碰巧正确，但调试起来非常难受。所以现在无论什么情况下调用inv_mod，第一行都会先a %= m，这个习惯算是长期换来的经验。