【题目描述】自从曹冲搞定了大象以后曹操就开始琢磨让儿子干些事业于是派他到中原养猪场养猪可是曹冲很不高兴于是在工作中马马虎虎有一次曹操想知道母猪的数量于是曹冲想狠狠耍曹操一把。举个例子假如有 16 头母猪如果建了 3 个猪圈剩下 1 头猪就没有地方安家了如果建造了 5 个猪圈但是仍然有 1 头猪没有地方去如果建造了 7 个猪圈还有 2 头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总你该怎么办【输入】第一行包含一个整数 n表示建立猪圈的次数接下来 n 行每行两个整数 ai,bi 表示建立了 ai个猪圈有 bi 头猪没有去处。你可以假定 ai,aj 互质。【输出】输出仅包含一个正整数即为曹冲至少养猪的数目。【输入样例】3 3 1 5 1 7 2【输出样例】16【提示】数据范围与提示对于全部数据1≤n≤10,1≤bi≤ai≤1000。各位备考 CSP-J/S 的同学大家好在数论模块的复习中我们经常会遇到一类“物不知数”的问题。很多同学初看题目觉得像脑筋急转弯但在信奥赛中这类问题有着极其成熟的解法。今天我们就以经典题目“曹冲养猪”为例带大家手把手推导并彻底拿下中国剩余定理CRT及其进阶版扩展中国剩余定理EXCRT。1. 题意转换一句话剥离背景题目描述了给定一系列除数猪圈数 ai和余数剩下的猪数 bi求被除数母猪总数 x的最小正整数值。本质数学模型求解一个一元线性同余方程组的最小正整数解x≡b1(moda1)x≡b2(moda2)…x≡bn(modan)题目中还给出了一个友好条件保证所有的 ai 两两互质。2. 思考过程与解题思路第一直觉的暴力解法是什么大家看到这道题最简单的直觉肯定是从 x1 开始一个一个往上枚举每次用一个for循环检查 x 是否满足所有的取模条件如果全都满足就输出。为什么会超时题目说明 n≤10,ai≤1000。虽然 n 不大但这些模数是互质的这意味着方程组的最小公共周期即最终答案的最大可能值是它们的乘积。最坏情况下x 可能会达到 1000^1010^30这简直是天文数字暴力枚举绝对会因为无尽的循环而超时。如何一步步推导到正解既然不能暴力搜我们就必须用代数的方法“解”出来。老祖宗的智慧CRT既然模数两两互质这完美契合了古代《孙子算经》中的解法。我们可以构造一个全局大周期然后针对每个方程单独构造一个“局部特解”最后把所有特解加起来。这就是中国剩余定理CRT。更高维的降维打击EXCRTCRT 虽好但有一个致命弱点——如果题目把“ai 两两互质”这个条件去掉CRT 就会当场失效。为了拥有一个通杀所有同余方程组的“万能兵器”我们不妨换个思路每次只看两个方程把它们合并成一个新方程然后不断两两合并直到只剩最后一个方程。这就引出了以扩欧exgcd为核心的扩展中国剩余定理EXCRT。3. 算法设计与样例推演这里我们重点讲解普适性更强、能够作为万能模板的EXCRT做法二。核心算法与状态转移设计假设我们已经合并了前 i−1 个方程算出了一个阶段性的答案ans此时前 i−1 个方程的最小公倍数总周期为lcm。 那么前 i−1 个方程的通解可以表示为xanslcm⋅t t 为任意整数。现在我们要把这个通解代入第 i 个方程要求满足anslcm⋅t≡bi(mod ai)移项把未知的 t 留在一边lcm⋅t≡bi−ans(mod ai)转化为普通的二元一次不定方程设辅助变量为 ylcm⋅tai⋅ybi−ans大家看这不就是标准的 AxByC 吗我们直接使用exgcd(lcm, a[i], t, y)解出步数 t再把 t 代回原来的通解公式更新ans和lcm就可以不断滚动合并下去了极简数据手玩推演带入输入样例方程1x≡1(mod 3)方程2x≡1(mod 5)方程3x≡2(mod 7)初始状态ans b11,lcm a13。此时已经满足方程1合并方程2要求 3⋅t1≡1(mod 5) ⟹ 3t≡0(mod 5)。解得最小的 t0。 更新基底ans 13×01。更新周期lcm lcm(3,5)15。合并方程3要求 15⋅t1≡2(mod 7)⟹15t≡1(mod 7)⟹1t≡1(mod 7)。解得最小的 t1。 更新基底ans 115×116。更新周期lcm lcm(15,7)105。最终结果16。与样例输出完全一致。4. 时空复杂度分析时间复杂度O(nlog(max(ai)))。总共进行 n 次方程合并每次合并调用一次exgcd。扩欧算法的时间复杂度是对数级别的非常快。对于 N≤10 而言运算次数不足百次耗时 0 ms。空间复杂度O(n)。只需要两个长度为 1010 的一维数组a和b存储模数和余数空间开销极小完全不可能MLE。5. 坑点与易错总结在运用 EXCRT 的时候有着非常多惨痛的工程暗坑大家一定要拿出小本本记好C 负数取模未定义行为在移项求目标常数 C 时bi−ans 极有可能是负数必须用黄金句型((b[i] - ans) % a[i] a[i]) % a[i]强制转正。数据类型溢出防范极其关键教练悄悄提醒虽然这道题数据较小但如果是国赛级别的题目输入变量a[i]和b[i]最好直接开long long否则在读入大数时就会瞬间溢出。在求真实 t 时ll t (t0 * times) % mod;如果mod非常大t0 * times会直接撑爆long long的极限。在更高阶的比赛中这里往往需要强制转为__int128即ll t ((__int128)t0 * times) % mod;来当防弹衣。周期必须同步缩小等式除以最大公约数 d 后解 t 的合法周期必须同步压缩为a[i] / d绝对不能对着原来的a[i]取模6. 标程详解下面给出包含了普通CRT与扩展CRT (EXCRT)的两个版本代码。请重点阅读EXCRT部分的详尽注释这是所有同余合并问题的终极模板//因为ai aj互质所以可以使用中国剩余定理也可以使用扩展中国剩余定理 //第一种做法先使用中国剩余定理来做 中国剩余定理要求模数必须是两两互质的 #include iostream using namespace std; int n; int a[1010];//建立猪圈数模数 int b[1010];//b[i]代表有a[i]个猪圈的情况下有多少头猪没有去处余数 long long M1;//存储所有模数的乘积 long long ans;//存储通解 即至少养猪的数目 long long xi,yi,d; long long exgcd(long long a,long long b,long long x,long long y){ if(b0){ x1; y0; return a; } dexgcd(b,a%b,x,y); long long tmpx; xy; ytmp-(a/b)*y; return d; } int main(){ cinn; for(int i1;in;i){ cina[i]b[i]; M*a[i];//存储所有模数的乘积 } for(int i1;in;i){ long long miM/a[i];//算出除了自己以外其他模数的乘积 dexgcd(mi,a[i],xi,yi); ans(ansmi*xi*b[i])%M; } cout(ansM)%M; }//第二种做法 扩展中国剩余定理 不管模数是否互质都可以使用 #include iostream using namespace std; int n; int a[1010];//建立猪圈数 模数 int b[1010];//b[i]代表有a[i]个猪圈的情况下有多少头猪没有去处 余数 typedef long long ll; //扩展欧几里得 ll exgcd(ll a,ll b,ll x,ll y){ if(b0){ x1; y0; return a; } ll dexgcd(b,a%b,x,y); ll tmpx; xy; ytmp-(a/b)*y; return d; } //扩展中国剩余定理 ll excrt(){ //第一步建立初始基底 把第1个方程当做地基 //ans代表当前已经拼出来的答案(数学公式里的x) ll ansb[1]; //lcm代表当前所有已合并方程的最小公倍数(数学公式里的M) ll lcma[1]; //当前满足第一个方程的通解为 anslcm*t(t为一个自己设的未知量) //接下来要去找第二个方程的通解 //所以就是要设一个t让anslcm*tb[2] (mod a[2]) //即lcm*tb[2]-ans(mod a[2]) //即lcm*ta[2]*yb[2]-ans //开始逐一合并第2到第n个方程 for(int i2;in;i){ //明确当前第i轮的目标方程 //数学推导目标 lcm*ta[i]*yb[i]-ans //b[i]-ans极有可能是负数 //必须用(c%mm)%m的写法将其转化为正数余数 ll c((b[i]-ans)%a[i]a[i])%a[i]; //接下来式子就变成了lcm*ta[i]*yc(axbyc的形式) //我们就可以用扩展欧几里得求出t和y //创建临时变量t0和y0 让扩欧去求基础特解 ll t0,y0; //扩欧解出的底层等式: lcm*t0a[i]*y0d ll dexgcd(lcm,a[i],t0,y0); //裴蜀定理拦截(无解情况) //如果目标常数不能被最大公约数整除 方程组彻底无解 if(c%d!0) return -1; ll moda[i]/d;//求出当前状态下的真实周期新模数 ll times(c/d)%mod;//算出放大倍数 并取模 防止溢出 //把临时变量t0转成最小正整数 t0(t0%modmod)%mod; //正式等比例放大 拿到真实且合法的t ll t(t0*times)%mod; //合并当前方程 更新大基底 //把这轮算出来的增量加到总答案上 ansanst*lcm; //更新总周期 为下一轮循环做准备(先除d后乘m[i] 不溢出) lcmlcm/d*a[i]; //保证总答案始终是最小正整数 ans(ans%lcmlcm)%lcm; } return ans; } int main(){ cinn; for(int i1;in;i) cina[i]b[i]; coutexcrt(); return 0; }
