题解 P4777 【【模板】扩展中国剩余定理（EXCRT）】

[博客原文食用更佳](https://blog.csdn.net/niiick/article/details/80229217) #### **问题** 求解同余方程组 $$\left\{\begin{aligned}x\equiv\ a_1(\mod m_1) \quad\\ x\equiv\ a_2(\mod m_2) \quad\\ x\equiv\ a_3(\mod m_3) \quad\\ ...\quad\\x\equiv\ a_k(\mod m_k) \quad\end{aligned}\right.$$ 其中$m_1,m_2,m_3...m_k$为**不一定两两互质**的整数， 求x的最小非负整数解 #### **求解** 假设已经求出前k-1个方程组成的同余方程组的一个解为x 且有$M=\prod_{i-1}^{k-1}m_i$ （补充：代码实现中用的就是$M=LCM_{i-1}^{k-1}m_i$，~~显然易证~~这样是对的，还更能防止溢出，上述是为了先方便理解，评论区就别问那么多次了=_=） 则前k-1个方程的方程组通解为$x+i*M(i\in Z)$ 那么对于加入第k个方程后的方程组 我们就是要求一个正整数t，使得 $x+t*M \equiv a_k(\mod m_k)$ 转化一下上述式子得 $t*M \equiv a_k-x(\mod m_k)$ 对于这个式子我们已经可以通过扩展欧几里得求解t 若该同余式无解，则整个方程组无解， 若有，则前k个同余式组成的方程组的一个解解为$x_k=x+t*M$ 所以整个算法的思路就是求解**k次扩展欧几里得** **另外，蒟蒻平常写题喜欢把后面一项看做b，所以输入和题目是反过来的** **输入和题目是反过来的，输入和题目是反过来的，输入和题目是反过来的** ```cpp //niiick #include<iostream> #include<vector> #include<algorithm> #include<queue> #include<cstring> #include<cstdio> using namespace std; typedef long long lt; lt read() { lt f=1,x=0; char ss=getchar(); while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();} while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();} return f*x; } const int maxn=100010; int n; lt ai[maxn],bi[maxn]; lt mul(lt a,lt b,lt mod) { lt res=0; while(b>0) { if(b&1) res=(res+a)%mod; a=(a+a)%mod; b>>=1; } return res; } lt exgcd(lt a,lt b,lt &x,lt &y) { if(b==0){x=1;y=0;return a;} lt gcd=exgcd(b,a%b,x,y); lt tp=x; x=y; y=tp-a/b*y; return gcd; } lt excrt() { lt x,y,k; lt M=bi[1],ans=ai[1];//第一个方程的解特判 for(int i=2;i<=n;i++) { lt a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;//ax≡c(mod b) lt gcd=exgcd(a,b,x,y),bg=b/gcd; if(c%gcd!=0) return -1; //判断是否无解，然而这题其实不用 x=mul(x,c/gcd,bg); ans+=x*M;//更新前k个方程组的答案 M*=bg;//M为前k个m的lcm ans=(ans%M+M)%M; } return (ans%M+M)%M; } int main() { n=read(); for(int i=1;i<=n;++i) bi[i]=read(),ai[i]=read(); printf("%lld",excrt()); return 0; } ``` ### update OI退役以后就不怎么上洛谷了，评论区似乎对代码部分疑问有点多，所以就更新一下细节，~~当年喜欢压行确实是个很不好的习惯~~ 针对一些对代码的疑问做点解答 > Q：c=(ai[i]-ans%b+b)%b是什么意思 我们推导出$t*M \equiv a_k-x(\mod m_k)$ 其中$a_k-x$对应$ax≡c(\mod b)$中的c，这句代码里$ans$对应$x$，$b$对应$m_k$ 所以这句话就是把$a_k-x$先对$m_k$取模 > Q：为啥不加个括号变成c=((ai[i]-ans)%b+b)%b ans%b的范围是[0,b-1)，a[i]-ans%b+b一定不会小于0的，当然加了也没问题 > Q：为什么$M*=bg$而不是$M*=b$ 这里bg=b/gcd(a,b)对应到推到部分公式里的就是$bg=m_k/gcd(m_k,LCM_{i=1}^{k-1}m_i)$ $M*=bg$明显就是令M为前k个m的最小公倍数 > Q：这句话x=mul(x,c/gcd,bg)为什么要乘c/gcd，为什么模数是bg 建议复习[扩展欧几里得](https://blog.csdn.net/niiick/article/details/80119121)