企业官网建设流程全解析

自从曹冲搞定了大象以后，曹操就开始琢磨让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲很不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。

举个例子，假如有 16 头母猪，如果建了 3 个猪圈，剩下 1 头猪就没有地方安家了；如果建造了 5 个猪圈，但是仍然有 1 头猪没有地方去；如果建造了 7 个猪圈，还有 2 头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？

第一行包含一个整数 n，表示建立猪圈的次数；

接下来 n 行，每行两个整数 ai,bi ，表示建立了 ai个猪圈，有 bi 头猪没有去处。你可以假定 ai,aj 互质。

输出仅包含一个正整数，即为曹冲至少养猪的数目。

数据范围与提示：

对于全部数据，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. 思考过程与解题思路

第一直觉的暴力解法是什么？大家看到这道题，最简单的直觉肯定是从 x=1 开始，一个一个往上枚举，每次用一个for循环检查 x 是否满足所有的取模条件，如果全都满足就输出。为什么会超时？题目说明 n≤10,ai​≤1000。虽然 n 不大，但这些模数是互质的，这意味着方程组的最小公共周期（即最终答案的最大可能值）是它们的乘积。最坏情况下，x 可能会达到 1000^10=10^30！这简直是天文数字，暴力枚举绝对会因为无尽的循环而超时。

如何一步步推导到正解？既然不能暴力搜，我们就必须用代数的方法“解”出来。

1. 老祖宗的智慧（CRT）：既然模数两两互质，这完美契合了古代《孙子算经》中的解法。我们可以构造一个全局大周期​，然后针对每个方程单独构造一个“局部特解”，最后把所有特解加起来。这就是中国剩余定理（CRT）。

2. 更高维的降维打击（EXCRT）：CRT 虽好，但有一个致命弱点——如果题目把“ai​ 两两互质”这个条件去掉，CRT 就会当场失效。为了拥有一个通杀所有同余方程组的“万能兵器”，我们不妨换个思路：每次只看两个方程，把它们合并成一个新方程，然后不断两两合并，直到只剩最后一个方程。这就引出了以扩欧（exgcd）为核心的扩展中国剩余定理（EXCRT）。

3. 算法设计与样例推演

这里我们重点讲解普适性更强、能够作为万能模板的EXCRT（做法二）。

核心算法与状态转移设计：假设我们已经合并了前 i−1 个方程，算出了一个阶段性的答案ans，此时前 i−1 个方程的最小公倍数（总周期）为lcm。 那么前 i−1 个方程的通解可以表示为：x=ans+lcm⋅t （t 为任意整数）。

现在，我们要把这个通解代入第 i 个方程，要求满足：

ans+lcm⋅t≡bi​(mod ai​)

移项，把未知的 t 留在一边：

lcm⋅t≡bi​−ans(mod ai​)

转化为普通的二元一次不定方程（设辅助变量为 y）：

lcm⋅t+ai​⋅y=bi​−ans

大家看，这不就是标准的 Ax+By=C 吗？我们直接使用exgcd(lcm, a[i], t, y)解出步数 t，再把 t 代回原来的通解公式更新ans和lcm，就可以不断滚动合并下去了！

极简数据手玩推演（带入输入样例）：

方程1：x≡1(mod 3)

方程2：x≡1(mod 5)

方程3：x≡2(mod 7)

• 初始状态：ans= b1​=1,lcm= a1​=3。（此时已经满足方程1）

• 合并方程2：要求 3⋅t+1≡1(mod 5) ⟹ 3t≡0(mod 5)。解得最小的 t=0。 更新基底：ans= 1+3×0=1。更新周期：lcm= lcm(3,5)=15。

• 合并方程3：要求 15⋅t+1≡2(mod 7)⟹15t≡1(mod 7)⟹1t≡1(mod 7)。解得最小的 t=1。 更新基底：ans= 1+15×1=16。更新周期：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 的时候，有着非常多惨痛的工程暗坑，大家一定要拿出小本本记好：

1. C++ 负数取模未定义行为：在移项求目标常数 C 时，bi​−ans 极有可能是负数，必须用黄金句型((b[i] - ans) % a[i] + a[i]) % a[i]强制转正。

2. 数据类型溢出防范（极其关键）：

   • 教练悄悄提醒：虽然这道题数据较小，但如果是国赛级别的题目，输入变量a[i]和b[i]最好直接开long long，否则在读入大数时就会瞬间溢出。

   • 在求真实 t 时：ll t = (t0 * times) % mod;如果mod非常大，t0 * times会直接撑爆long long的极限。在更高阶的比赛中，这里往往需要强制转为__int128即ll t = ((__int128)t0 * times) % mod;来当防弹衣。

3. 周期必须同步缩小：等式除以最大公约数 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 M=1;//存储所有模数的乘积 long long ans;//存储通解 即至少养猪的数目 long long xi,yi,d; long long exgcd(long long a,long long b,long long &x,long long &y){ if(b==0){ x=1; y=0; return a; } d=exgcd(b,a%b,x,y); long long tmp=x; x=y; y=tmp-(a/b)*y; return d; } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]>>b[i]; M*=a[i];//存储所有模数的乘积 } for(int i=1;i<=n;i++){ long long mi=M/a[i];//算出除了自己以外其他模数的乘积 d=exgcd(mi,a[i],xi,yi); ans=(ans+mi*xi*b[i])%M; } cout<<(ans+M)%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(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(){ //第一步：建立初始基底 把第1个方程当做地基 //ans代表当前已经拼出来的答案(数学公式里的x) ll ans=b[1]; //lcm代表当前所有已合并方程的最小公倍数(数学公式里的M) ll lcm=a[1]; //当前满足第一个方程的通解为 ans+lcm*t(t为一个自己设的未知量) //接下来要去找第二个方程的通解 //所以就是要设一个t让ans+lcm*t=b[2] (mod a[2]) //即lcm*t=b[2]-ans(mod a[2]) //即lcm*t+a[2]*y=b[2]-ans //开始逐一合并第2到第n个方程 for(int i=2;i<=n;i++){ //明确当前第i轮的目标方程 //数学推导目标 lcm*t+a[i]*y=b[i]-ans //b[i]-ans极有可能是负数 //必须用(c%m+m)%m的写法将其转化为正数余数 ll c=((b[i]-ans)%a[i]+a[i])%a[i]; //接下来式子就变成了lcm*t+a[i]*y=c(ax+by=c的形式) //我们就可以用扩展欧几里得求出t和y //创建临时变量t0和y0 让扩欧去求基础特解 ll t0,y0; //扩欧解出的底层等式: lcm*t0+a[i]*y0=d ll d=exgcd(lcm,a[i],t0,y0); //裴蜀定理拦截(无解情况) //如果目标常数不能被最大公约数整除 方程组彻底无解 if(c%d!=0) return -1; ll mod=a[i]/d;//求出当前状态下的真实周期（新模数） ll times=(c/d)%mod;//算出放大倍数 并取模 防止溢出 //把临时变量t0转成最小正整数 t0=(t0%mod+mod)%mod; //正式等比例放大 拿到真实且合法的t ll t=(t0*times)%mod; //合并当前方程 更新大基底 //把这轮算出来的增量加到总答案上 ans=ans+t*lcm; //更新总周期 为下一轮循环做准备(先除d后乘m[i] 不溢出) lcm=lcm/d*a[i]; //保证总答案始终是最小正整数 ans=(ans%lcm+lcm)%lcm; } return ans; } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]; cout<<excrt(); return 0; }