学习笔记 - 扩展中国剩余定理

以前的blog好像写错了……（懒得改了）
重新学了一遍~

---

· 引入

$$\begin{cases} x\equiv r_1\pmod {m_1}\\ x\equiv r_2\pmod {m_2}\\ ...\\ x\equiv r_n\pmod {m_n} \end{cases}$$

求解上述关于 $x$ 的方程组。（参考 #hihocoder 1303#）

此类方程组称为 模线性方程组。求解此类问题的一般方法就是扩展中国剩余定理，当然方程组可能无解。

---

· 扩展中国剩余定理

- 前置

① 扩展欧几里得定理；
② 同余方程；

- 推导

首先我们考虑 $n=2$ ，即方程组只有两个式子。

根据同余的定义，我们可以写出：

$$\begin{cases} x\equiv r_1\pmod{m_1}\\ x\equiv r_2\pmod{m_2} \end{cases} \Longrightarrow \begin{cases} x=k_1m_1+r_1\\ x=k_2m_2+r_2 \end{cases}$$

所以有 $k_1m_1+r_1=k_2m_2+r_2$ ；
移项得：$k_1m_1-k_2m_2=r_2-r_1​$ ；

令 $g=\gcd(m_1,m_2)$ ，将上式两边同时除以 $g$ ，得： $\frac{m_1}{g}k_1-\frac{m_2}{g}k_2=\frac{r_2-r_1}{g}$ ；
（★）因为上式的左边一定是整数，如果右边是分数，即 $g\not| r_2-r_1$ ，方程就无解；反之方程有解；

判断如果有解，则有 $\frac{m_1}{g}k_1-\frac{m_2}{g}k_2=\frac{r_2-r_1}{g}$ 。
因为 $\gcd(\frac{m_1}{g},\frac{m_2}{g})=1$，通过扩展欧几里得定理我们可以得到一组 $(k_1’,k_2’)$ 满足 $\frac{m_1}{g}k_1’+\frac{m_2}{g}k_2’=1$ ；
再将上式两边同时乘以 $t=\frac{r_2-r_1}{g}$ ，得：$\frac{m_1}{g}(k_1’t)-\frac{m_2}{g}(k_2’t)=t$ ；
则有：

$$\begin{cases} k_1m_1-k_2m_2=tg\\ k_1'tm_1+k_2'tm_2=tg \end{cases} \Longrightarrow \begin{cases} k_1\equiv k_1't\pmod{\frac{m_2}{g}}\\ k_2\equiv k_2't\pmod{\frac{m_1}{g}} \end{cases}$$

那么就可以得到 $x​$ 的一个最小解 $x=k_1m_1+r_1​$ ；
令 $l​$ 为 $m_1,m_2​$ 的最小公倍数，根据这个解我们可以得到一个解集：$X=\{kl+x|k\in R\}​$ ；
则对于 $X_i\in X​$ 有 $X_i\equiv x\pmod{l}​$ ；

- C++实现

显然可以递推，设上一步得到了 $x\equiv R\pmod{M}$；则有：

$$\begin{cases} x\equiv R\pmod{M}\\ x\equiv r_i\pmod{m_i} \end{cases}$$

通过欧几里得定理得到 g=GCD(M,m[i])​；
定义 C=r[i]-R​；

根据扩展中国剩余定理，若 C%g!=0 ，则无解；

否则通过扩展欧几里得定理EXGCD(M/g,m[i]/g,k1,k2)，可以得到 k1；
然后 x=(C/g*k1)%(m[i]/g) 得到 x 的最小解。

更新 R,M ：R=R+x*M，M=M*m[i]/g（也就是M和m[i]的最小公倍数）；
使 R 的绝对值尽可能小：R=R%M。

- 伪代码

M=m[1],R=r[1]
For i=2~n
	C = r[i]-R
	g = GCD( M , m[i] )
	If R mod C != 0
		无解
	（ k1 , k2 ）= EXGCD( M / g , m[i] / g )
	x = ( C / g * k1 ) mod ( m[i] / g )
	R = R + x * M
	M = LCM( M , m[i] )
	R = R mod M
答案为 R //正数解为 (R+M)%M

---

· 源代码

（以 hihocoder 1303 为参考）

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1000;
ll m[N+3],r[N+3];
ll GCD(ll A,ll B){
	return B? GCD(B,A%B):A;
}
ll EXGCD(ll a,ll b,ll &x1,ll &y1){
	if(b){
		ll x2,y2;
		ll res=EXGCD(b,a%b,x2,y2);
		x1=y2;
		y1=x2-a/b*y2;
		return res;
	}
	else{
		x1=1;
		y1=0;
		return a;
	}
}
ll GetInv(ll a,ll p){ //inv*a+k*p=1
	ll inv,k;
	EXGCD(a,p,inv,k);
	return inv;
}
int main(){
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&m[i],&r[i]);
	ll M=m[1],R=r[1];
	for(int i=2;i<=n;i++){
		ll g=GCD(M,m[i]);
		ll C=r[i]-R;
		if(C%g) printf("-1\n"),exit(0);
		ll k1,k2;
		EXGCD(M/g,m[i]/g,k1,k2);
		k1=(C/g*k1)%(m[i]/g);
		R+=k1*M;
		M=M/g*m[i];
		R%=M;
	}
	printf("%lld\n",(R+M)%M);
	return 0;
}

---

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ，欢迎提问~