中国剩余定理与拓展

• 中国剩余定理又称孙子定理
• 是处理一次同余方程组求解问题的一个基本结论
• 可以用于求解模线性方程组的解

中国剩余定理（CRT）

求解如下的方程组
$\begin{cases}x\equiv b_1\pmod{m_1}\\x\equiv b_2\pmod{m_2}\\x\equiv b_3\pmod{m_3}\\\dots\\x\equiv b_n\pmod{m_n}\end{cases}$
有$M=\prod_{i=1}^nm_i$
$M_i=M/m_i,y_i\equiv M_i \pmod{m_i},y_i$是在模$m_i$意义下的逆元
$m_i(1\le i\le n)$两两互素
此方程组在$\mod M$意义下有唯一解
此解可表示为
$x\equiv \sum_{i=1}^naiM_iy_i \pmod{M}$

ll china(){
	ll ans=0;
	ll M=1;
	for(int i=1;i<=n;++i){
		M*=ai[i];
	}
	for(int i=1;i<=n;++i){
		ll kk=M/ai[i];
		ll x=0,y=0;
		exgcd(kk,ai[i],x,y);
		ans=(ans+bi[i]*kk*x)%M;
	}
	if(ans>0){
		return ans;
	}else{
		return ans+M;
	}
}

拓展中国剩余定理（EXCRT）

拓展中国剩余定理可以用于求解在中国剩余定理中$m_i(1\le i\le n)$不互素的情况
求解如下的方程组
$\begin{cases}x\equiv c_1\pmod{m_1}\\x\equiv c_2\pmod{m_2}\\x\equiv c_3\pmod{m_3}\\\dots\\x\equiv c_n\pmod{m_n}\end{cases}$
$m_i(1\le i\le n)$不保证两两互素
解题思路主要是将两两方程合并
最后化为一个方程组进行求解
首先考虑只有两个方程组的情况
$\begin{cases}x\equiv c_1\pmod{m_1}\\x\equiv c_2\pmod{m_2} \end{cases}$
有
$x=k_1\times m_1+c_1$……（1）
$x=k_2\times m_2+c_2$
$k_1\times m_1+c_1=k_2\times m_2+c_2$
$k_1\times m_1=k_2\times m_2+(c_2-c_1)$
此时，$k_1\times m_1-k_2\times m_2=c_2-c_1$,$(m_1,m_2)|(c_2-c_1)$否则方程无解
令 $d=(m_1,m_2)$
$\frac {m_1}{d}\times k_1=\frac{m_2}{d}\times k_2+\frac {c_2-c_1}{d}$
$\frac{m_1}{d}\times k_1\equiv \frac{c_2-c_1}{d}\pmod{\frac{m_2}{d}}$
在此，我们消掉了$k_1$
等式两边同除$\frac {m_1}{d}$
由同余的同除性质（第八条），详情
$k_1\equiv \frac {c_2-c_1}{d}\times inv(\frac{m_1}{d},\frac{m_2}{d})\pmod{\frac{m_2}{d}}$
$inv(x,y)$表示x在模y意义下的逆元
有
$k_1=\frac{c_2-c_1}{d}\times inv(\frac{m_1}{d},\frac{m_2}{d})+y\times \frac {m_2}{d}$
将上式代回（1）
$x=\frac {c_2-c_1}{d}\times inv(\frac{m_1}{d},\frac{m_2}{d})\times m_1+y\times \frac {m_1\times m_2}{d}+c_1$
$x\equiv \frac {c_2-c_1}{d}\times inv(\frac{m_1}{d},\frac{m_2}{d})\times m_1+c_1\pmod{\frac{m_1\times m_2}{d}}$
此时发现这个式子又是$x\equiv c\pmod{m}$的形式
其中
$m=\frac{m_1\times m_2}{d}$
$c=\frac {c_2-c_1}{d}\times inv(\frac{m_1}{d},\frac{m_2}{d})\times m_1+c_1$
当最只有一个方程组时，c自然为答案

ll excrt(){
	ll M=ai[1];
	ll ans=bi[1];
	for(int i=2;i<=n;++i){
		ll e=bi[i]-ans;
		ll x,y;
		ll d=exgcd(M,ai[i],x,y);
		if(e%d!=0){ return -1;}
		ll nowm=ai[i]/d;
		x=(x%nowm+nowm)%nowm;
		x=(mul(x,(e/d%nowm+nowm)%nowm,nowm)+nowm)%nowm;
		ll newm=M*nowm;
		ans=(ans+mul(x,M,newm)+newm)%newm;
		M=newm;
	}
	return ans;
}

ps:
坑：在计算机中，若有a<0，则a mod b仍然是负数，与数学中的定义不一致
所以，频繁的取+mod,再取mod操作是为了保证mod后为正整数，与数学中的定义保持一致

从另一角度理解代码中的exgcd

两方程组
$\begin{cases}x\equiv c_1\pmod{m_1}\\x\equiv c_2\pmod{m_2} \end{cases}$
同上化简
$k_1\times m_1-k_2\times m_2=c_2-c_1$
此时$m_1,m_2$不一定互质
令$d=(m_1,m_2)$
$m_1=m_1'\times d,m_2=m_2'\times d,m_1',m_2'$互质
则$exgcd(m_1,m_2,x,y)$求解了
$m_1'\times k_1'+m_2'\times k_2'=1$的一个解
则上式$k_1\times m_1-k_2\times m_2=c_2-c_1$中的$k_1=k_1'\times \frac{c_2-c_1}{d}+p\times m_2',m_2'=\frac{m_2}{d}$