中国剩余定理 && 扩展中国剩余定理

全栈程序员-站长 • 2026年3月19日下午9:51 • 未分类 • 阅读 2

中国剩余定理

问题

定理

令 $M=\prod_{i=1}^km_i$ ，即M是所有 $m_i$ 的最小公倍数

$t_i$ 为同余方程 $\frac{M}{m_i}t_i \equiv\ 1(\mod m_i)$ 的最小非负整数解

则有一个解为 $x=\sum_{i=1}^ka_i\frac{M}{m_i}t_i$

通解为 $x+i*M(i\in Z)$
特别的，最小非负整数解为 $(x$ % $M + M)$ % $M$

证明

因为 $\frac{M}{m_i}$ 是除 $m_i$ 之外的所有m的倍数
所以 $\forall k \not= i, a_i\frac{M}{m_i}t_i \equiv 0(\mod m_k)$
又有 $\frac{M}{m_i}t_i \equiv\ 1(\mod m_i)$
两边同时乘 $a_i$ 得 $a_i\frac{M}{m_i}t_i \equiv a_i(\mod m_i)$
带入 $x=\sum_{i=1}^ka_i\frac{M}{m_i}t_i$
原方程组成立
——算法竞赛进阶指南

代码实现

$t_i$ 同余式的求解可以用扩展欧几里得

void exgcd(int a,int b,int &x,int &y) { 
    if(b==0){ 
    x=1; y=0; return;} exgcd(b,a%b,x,y); int tp=x; x=y; y=tp-a/b*y; } int china() { 
    int ans=0,lcm=1,x,y; for(int i=1;i<=k;++i) lcm*=b[i]; for(int i=1;i<=k;++i) { 
    int tp=lcm/b[i]; exgcd(tp,b[i],x,y); x=(x%b[i]+b[i])%b[i];//x要为最小非负整数解 ans=(ans+tp*x*a[i])%lcm; } return (ans+lcm)%lcm; }

一道模板题

洛谷P3868 [TJOI2009]猜数字题解

扩展中国剩余定理

问题

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

求解

所以整个算法的思路就是求解k次扩展欧几里得

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; }

update

针对一些对代码的疑问做点解答

Q：c=(ai[i]-ans%b+b)%b是什么意思

我们推导出 $\equiv a_k-x(\mod m_k)$
其中 $a_k-x$ 对应 $ax≡c(\mod b)$ 中的c，这句代码里 $a n s$ 对应 $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 * = b g$ 而不是 $M * = b$

这里bg=b/gcd(a,b)对应到推到部分公式里的就是 $bg=m_k/gcd(m_k,LCM_{i=1}^{k-1}m_i)$
$M * = b g$ 明显就是令M为前k个m的最小公倍数

Q：这句话x=mul(x,c/gcd,bg)为什么要乘c/gcd，为什么模数是bg

建议复习扩展欧几里得

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/203418.html原文链接：https://javaforall.net

中国剩余定理 && 扩展中国剩余定理