企业官网建设流程全解析

原题来自：POJ 2891

给定 2n 个正整数 a1,a2,⋯,an和 m1,m2,⋯,m[n] ，求一个最小的正整数 x，满足 ∀i∈[1,n],x≡ai(mod m[i])，或者给出无解。

多组数据。

每组数据第一行一个整数 n；

接下来 n 行，每行两个整数 mi,ai 。

对于每组数据，若无解，输出 −1；否则输出一个非负整数，若有多解，输出最小的满足条件的答案。

数据范围与提示：

对于全部数据，所有的输入都是非负的，并且可以用 64 位有符号整数表示。保证 1≤n≤10^5,m[i]>a[i] 。

1. 题意转换

用一句话剥离题目的背景故事，这道题本质上是在求：给定 n 个线性同余方程 x ≡ a[i]​ (mod m[i]​)，在不保证模数m[i]两两互质的情况下，求出最小的正整数解 x。这正是数论中大名鼎鼎的终极武器——扩展中国剩余定理（EXCRT）的标准模板题。这道题是数论进阶阶段的绝佳试金石。

2. 思考过程与解题思路

面对方程组，我们的大脑通常会经历以下迭代过程：

• 第一直觉：暴力枚举最朴素的想法是，从 x=a[1]​ 开始，每次加上 m[1]​，然后去试是否满足第二个方程 x≡a[2]​(mod m[2]​)，满足后再去试第三个……为什么会超时？题目中 n≤10^5，模数虽然题目说 64 位整型装得下，但全部乘起来（即总周期）是一个天文数字。靠加法去遍历状态空间，评测机跑到宇宙毁灭也算不完。

• 降维打击：两两合并，化繁为简既然不能宏观通杀，我们就“微观蚕食”。假设我们已经处理完了前 i−1 个方程，求出了一个能同时满足它们的特解 ans。同时，前 i−1 个方程会形成一个公共大周期 lcm。 那么，前 i−1 个方程的“通解”就可以写成：x=ans+t⋅lcm （t 是未知的整数步数）。

  现在，我们要让这个通解也满足第 i 个方程：

  ans+t⋅lcm≡a[i]​ (mod m[i]​)

  稍微移一下项，把未知数放左边，已知常数放右边：

  t⋅lcm−y⋅m[i]​=a[i]​−ans

  仔细观察，这不就是一个标准的二元一次不定方程 Ax+By=C 吗？其中 A=lcm，B=m[i​]，C=a[i]​−ans。未知数是我们想求的步数 t（对应代码里的 x0​）。 迷雾彻底散开——直接掏出扩展欧几里得算法求解即可。

3. 算法设计与样例推演

标程的核心算法是exgcd + 迭代合并。 我们维护两个核心变量：

1. ans：当前已经合并成功的所有方程的最小正整数解（基底）。

2. lcm：当前已经合并成功的所有方程的最小公倍数（大周期）。

核心状态转移方程式：

1. 算常数：C=( (a[i]​−ans) (mod m[i]​) + m[i]​) (mod m[i]​)

2. 扩欧解基底：lcm⋅x0​+m[i]​⋅y0​=d=gcd(lcm,m[i]​)

3. 判无解：根据裴蜀定理，如果 C 不能被 d 整除，直接return -1。

4. 扩倍数求真实步长：t=(x0​⋅C/d)(mod m[i]/d)

5. 更新全局解：ans=(ans+t⋅lcm) (mod next_lcm)

极简数据手玩推演（带入样例数据）：方程 1：x≡7 (mod 8) 方程 2：x≡9 (mod 11)

• 初始状态：ans = 7,lcm = 8

• 接入方程 2：

  • 常数 C=9−7=2。

  • 调用exgcd(8, 11, x0, y0)：算出 8⋅(−4)+11⋅3=1。得出 d=1, x0=−4。

  • 计算局部周期：mod=m[i]​/d=11/1=11。

  • 步数扩大并转正：x0=(−4×2)(mod 11)≡−8≡3 (mod 11)。所以我们要跨 3 步。

  • 计算下一轮总周期：next_lcm=8/1×11=88。

  • 更新全局解：ans=(7+3×8) (mod 88)=31。

• 结果：输出 31，与样例完美契合。

4. 时空复杂度分析

• 时间复杂度：O(nlog(max M))。算法共有 n 轮循环，每次循环执行一次exgcd。扩展欧几里得的时间复杂度是对数级别的，整体跑满 10^5 次大约仅需十几毫秒，对于 1s 的时限绰绰有余。

• 空间复杂度：O(n)。仅需要开两个长度为 100010 的long long数组存储输入的 a 和 m，内存消耗不足 2 MB。

5. 易错总结

很多同学在手推扩展中国剩余定理时，经常被代码里满天飞的取模搞晕。什么时候该% mod，什么时候该% lcm？这是一个极其敏锐且直击本质的问题！这两类取模的作用对象完全不同：

灵魂拷问 1：为什么求 x0​ 时要% mod？

% mod是用来约束倍数（系数 x0）的。 在第 i 轮时，为了让新方程成立，我们移项得到了方程：

x0​⋅lcm+y0⋅m[i]​=c

此时，我们求出了最大公约数 d=gcd(lcm,m[i]​)。把方程两边同时除以 d，转换回同余方程：

x0⋅lcm/d≡c/d​ (mod m[i]/d​​)

在这个化简后的方程里，x0 的周期（也就是新的模数）变成了m[i]/d。这正是代码中ll mod = m[i] / d;的由来。我们对 x0​ 进行% mod操作，是为了在局部方程里找到满足条件的最小正倍数，防止 x0 变得无穷大导致后续乘法溢出。

灵魂拷问 2：为什么更新答案时要% lcm(或% nextlcm)？

% lcm是用来约束真实答案（ans）的。 当我们求出了最小正倍数 x0 后，就算出了满足前 i 个方程的新解：ans[new​]=ans+x0​⋅lcm。 但这只是无穷多个合法解中的一个。前 i 个方程合并后，它们会有一个全局的总循环周期。这个周期就是原本的 lcm 和当前模数 mi​ 的最小公倍数，即：

nextlcm=lcm⋅m[i]/d​​

因为题目要求的是最小正整数解，所以无论 ans[new]​变到多大，它相对于新的大周期 nextlcm 的余数才是最小的合法答案。

核心总结对照表：

一句话概括：算未知数 x0 用小模数 (mod)，算大答案 ans 用大模数 (lcm)。

其他易错点：

• 多组数据与 EOF 读入：题目明确说明“多组数据”，必须写while(cin >> n)。

• 输入顺序陷阱：POJ 2891 的输入格式是先给模数 m[i]​，再给余数 a[i]​。直接读错位会导致底层扩欧彻底错误。

• 溢出与__int128：大整数相乘如x0*lcm在极端数据下可能会撑爆long long，建议套上__int128，但是不写也能过。

6. 完整代码

//因为不确定模数是否互质 所以使用扩展中国剩余定理 #include <iostream> using namespace std; int n; long long a[100010];//a[i]与m[i]对应，代表第m个式子的模数情况下所对应余数 long long m[100010];//m[i]代表第i个式子的模数 typedef long long ll; //扩展欧几里得 //求ax+by=gcd(a,b)的特解 并返回最大公约数d ll exgcd(ll a,ll b,ll &x_,ll &y_){ if(b==0){ x_=1; y_=0; return a; } ll d=exgcd(b,a%b,x_,y_); ll tmp=x_; x_=y_; y_=tmp-(a/b)*y_; return d; } //扩展中国剩余定理 ll excrt(){ ll ans=a[1];//满足第一个式子的结果（解） //lcm代表当前所有合并方程的最小公倍数 这里是第一个方程的模数 ll lcm=m[1]; //每一轮的方程都要满足 for(int i=2;i<=n;i++){ ll x0,y0; //要前一轮的式子满足后一轮的要求 则代表第i轮的目标方程为 //ans+x0*lcm≡a[i] (mod m[i]) （x0是这一轮新设的未知量 代表加x0个lcm可以满足要求） //移项 lcm*x0+m[i]*y0=a[i]-ans (y0是这一轮新设的未知量) //创建一个变量c=a[i]-ans ll c=a[i]-ans; //c有可能为负数 把c取正 c=(c%m[i]+m[i])%m[i]; //扩展欧几里得求解d和x0 lcm*x0+m[i]*y0=d ll d=exgcd(lcm,m[i],x0,y0); //根据裴蜀定理 如果c不能被d整除，则无解 if(c%d!=0) return -1; //算出要扩大的倍数 因为exgcd求的是lcm*x0+m[i]*y0=d的情况 //求lcm*x0+m[i]*y0=c x0 y0肯定要相应扩大 ll times=c/d; //模数要相应变化 等式两边同除以d后 局部运算的周期变为m[i]/d ll mod=m[i]/d; //把x0从可能的负数先转化成百分百的正数 x0=(x0%mod+mod)%mod; //等比例扩大x0 x0=(x0*times)%mod; //下一轮总周期 ll nextlcm=lcm/d*m[i]; //这一轮的解 //更新全局答案=旧答案+跨越的步数*旧周期 //更新完毕后，必须对新的全局周期nextlcm取模 ans=(ans+x0*lcm)%nextlcm; //更新总周期 lcm=nextlcm; //确保总答案是最小正整数 ans=(ans%lcm+lcm)%lcm; } return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(0); while(cin>>n){ for(int i=1;i<=n;i++) cin>>m[i]>>a[i]; //扩展中国剩余定理求解 cout<<excrt()<<"\n"; } return 0; }