【题目描述】原题来自POJ 2891给定 2n 个正整数 a1,a2,⋯,an和 m1,m2,⋯,m[n] 求一个最小的正整数 x满足 ∀i∈[1,n],x≡ai(mod m[i])或者给出无解。【输入】多组数据。每组数据第一行一个整数 n接下来 n 行每行两个整数 mi,ai 。【输出】对于每组数据若无解输出 −1否则输出一个非负整数若有多解输出最小的满足条件的答案。【输入样例】2 8 7 11 9【输出样例】31【提示】数据范围与提示对于全部数据所有的输入都是非负的并且可以用 64 位有符号整数表示。保证 1≤n≤10^5,m[i]a[i] 。1. 题意转换用一句话剥离题目的背景故事这道题本质上是在求给定 n 个线性同余方程 x ≡ a[i]​ (mod m[i]​)在不保证模数m[i]两两互质的情况下求出最小的正整数解 x。这正是数论中大名鼎鼎的终极武器——扩展中国剩余定理EXCRT的标准模板题。这道题是数论进阶阶段的绝佳试金石。2. 思考过程与解题思路面对方程组我们的大脑通常会经历以下迭代过程第一直觉暴力枚举最朴素的想法是从 xa[1]​ 开始每次加上 m[1]​然后去试是否满足第二个方程 x≡a[2]​(mod m[2]​)满足后再去试第三个……为什么会超时题目中 n≤10^5模数虽然题目说 64 位整型装得下但全部乘起来即总周期是一个天文数字。靠加法去遍历状态空间评测机跑到宇宙毁灭也算不完。降维打击两两合并化繁为简既然不能宏观通杀我们就“微观蚕食”。假设我们已经处理完了前 i−1 个方程求出了一个能同时满足它们的特解 ans。同时前 i−1 个方程会形成一个公共大周期 lcm。 那么前 i−1 个方程的“通解”就可以写成xanst⋅lcm t 是未知的整数步数。现在我们要让这个通解也满足第 i 个方程anst⋅lcm≡a[i]​ (mod m[i]​)稍微移一下项把未知数放左边已知常数放右边t⋅lcm−y⋅m[i]​a[i]​−ans仔细观察这不就是一个标准的二元一次不定方程 AxByC 吗其中 AlcmBm[i​]Ca[i]​−ans。未知数是我们想求的步数 t对应代码里的 x0​。 迷雾彻底散开——直接掏出扩展欧几里得算法求解即可。3. 算法设计与样例推演标程的核心算法是exgcd 迭代合并。 我们维护两个核心变量ans当前已经合并成功的所有方程的最小正整数解基底。lcm当前已经合并成功的所有方程的最小公倍数大周期。核心状态转移方程式算常数C( (a[i]​−ans) (mod m[i]​) m[i]​) (mod m[i]​)扩欧解基底lcm⋅x0​m[i]​⋅y0​dgcd(lcm,m[i]​)判无解根据裴蜀定理如果 C 不能被 d 整除直接return -1。扩倍数求真实步长t(x0​⋅C/d)(mod m[i]/d)更新全局解ans(anst⋅lcm) (mod next_lcm)极简数据手玩推演带入样例数据方程 1x≡7 (mod 8) 方程 2x≡9 (mod 11)初始状态ans 7,lcm 8接入方程 2常数 C9−72。调用exgcd(8, 11, x0, y0)算出 8⋅(−4)11⋅31。得出 d1, x0−4。计算局部周期modm[i]​/d11/111。步数扩大并转正x0(−4×2)(mod 11)≡−8≡3 (mod 11)。所以我们要跨 3 步。计算下一轮总周期next_lcm8/1×1188。更新全局解ans(73×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​⋅lcmy0⋅m[i]​c此时我们求出了最大公约数 dgcd(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​]ansx0​⋅lcm。 但这只是无穷多个合法解中的一个。前 i 个方程合并后它们会有一个全局的总循环周期。这个周期就是原本的 lcm 和当前模数 mi​ 的最小公倍数即nextlcmlcm⋅m[i]/d​​因为题目要求的是最小正整数解所以无论 ans[new]​变到多大它相对于新的大周期 nextlcm 的余数才是最小的合法答案。核心总结对照表变量物理意义所在的方程空间对应的模数代码中的变量名x0​需要跨越多少步才能满足当前方程局部的倍数空间m[i]​/dmodans满足当前所有方程的具体数值解全局的真实值空间lcm 与 m[i]​ 的最小公倍数nextlcm或更新后的lcm一句话概括算未知数 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; //扩展欧几里得 //求axbygcd(a,b)的特解 并返回最大公约数d ll exgcd(ll a,ll b,ll x_,ll y_){ if(b0){ x_1; y_0; return a; } ll dexgcd(b,a%b,x_,y_); ll tmpx_; x_y_; y_tmp-(a/b)*y_; return d; } //扩展中国剩余定理 ll excrt(){ ll ansa[1];//满足第一个式子的结果解 //lcm代表当前所有合并方程的最小公倍数 这里是第一个方程的模数 ll lcmm[1]; //每一轮的方程都要满足 for(int i2;in;i){ ll x0,y0; //要前一轮的式子满足后一轮的要求 则代表第i轮的目标方程为 //ansx0*lcm≡a[i] (mod m[i]) x0是这一轮新设的未知量 代表加x0个lcm可以满足要求 //移项 lcm*x0m[i]*y0a[i]-ans (y0是这一轮新设的未知量) //创建一个变量ca[i]-ans ll ca[i]-ans; //c有可能为负数 把c取正 c(c%m[i]m[i])%m[i]; //扩展欧几里得求解d和x0 lcm*x0m[i]*y0d ll dexgcd(lcm,m[i],x0,y0); //根据裴蜀定理 如果c不能被d整除则无解 if(c%d!0) return -1; //算出要扩大的倍数 因为exgcd求的是lcm*x0m[i]*y0d的情况 //求lcm*x0m[i]*y0c x0 y0肯定要相应扩大 ll timesc/d; //模数要相应变化 等式两边同除以d后 局部运算的周期变为m[i]/d ll modm[i]/d; //把x0从可能的负数先转化成百分百的正数 x0(x0%modmod)%mod; //等比例扩大x0 x0(x0*times)%mod; //下一轮总周期 ll nextlcmlcm/d*m[i]; //这一轮的解 //更新全局答案旧答案跨越的步数*旧周期 //更新完毕后必须对新的全局周期nextlcm取模 ans(ansx0*lcm)%nextlcm; //更新总周期 lcmnextlcm; //确保总答案是最小正整数 ans(ans%lcmlcm)%lcm; } return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(0); while(cinn){ for(int i1;in;i) cinm[i]a[i]; //扩展中国剩余定理求解 coutexcrt()\n; } return 0; }