东灯的寒舍

你特别好，我喜欢你

0%

中国剩余定理

Posted on Edited on In

Native

中国剩余定理用于求解线性同余方程组。

描述为：

设自然数 $m_1,m_2,m_3,…,m_r$ 两两互质，并记 $M=\prod^r_{i=1}m_i$，则

在模 $M$ 同余的意义下有唯一解。

求解

上面的看的太不明白了，让我们看着定理内容倒推证明一下正确性：

我们设 $M_i=\frac{M}{m_1}$，再假设 $t_i=M^{-1} (mod \ m_i)$ 那么 $x$ 的通解为 $x=a_1t_1M_1+a_2t_2M_2+…+a_nt_nM_n+KM,K\in\mathbb{Z}$

为什么呢，我们下面给出证明：

  • 对于刚才那组加和中$i$不是自己的情况(比如设 $i\not=j$)，那么 $m_i|M_j$，因此 $a_jt_jM_j\equiv0(mod \ m_i)$，所以它的贡献是没有的。

  • 那么如果 $i=j$，$t_iM_i\equiv1(mod \ m_i)$，对总解的贡献仅有 $a_i$，因此对于每个方程可以满足 $x\equiv a_i(mod \ m_i)$。

  • 最后通解加上了 $KM$，显然可以由同理第一条证明。

由此我们通过先看通解构造再反证明的方式证明了中国剩余定理的正确性。

实现

逆元采用 $exgcd$ 求得，但是因为 $m_i$ 之间两两互质，使用费马小也是可以的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define MAXN 10050
int W[MAXN],B[MAXN],k;
//有k组形如X≡B[i](mod W[i])的式子
void exgcd(int a,int b,int &x,int &y){
	if(!b){x=1,y=0;return;}
	exgcd(b,a%b,x,y);
	int temp=x;x=y;y=temp-(a/b)*y;
}
int China_Solve(){
	int N=1,M,x,y,Ans=0;
	for(int i=1;i<=k;++i)N*=W[i];
	for(int i=1;i<=k;++i){
		M=N/W[i];
		exgcd(W[i],M,x,y);
		Ans=(Ans+y*M*B[i])%N;
	}
	return Ans>0?Ans:Ans+N;
}

拓展中国剩余定理$(EXCRT)$

可以说和中国剩余定理基本上毫无关系，但是可以解决比中国剩余定理更广的问题。

当前问题变为：$m_i$ 之间如果两两并不互质，如何求解刚才的线性同余方程组？

先分析一下现在的问题处境：

  • $m_i$ 之间不互质，中国剩余定理不成立，所以其实这个方程不一定有解。
  • $m_i$ 之间不互质，最戳中中国剩余定理的一个点其实是中国剩余定理所作为基础的 $M$ 不存在（这个看下面的同余方程合并就知道为什么了）。
  • $m_i$ 之间不互质，中国剩余定理所基于的逆元也不存在（或者说不正确），因此上面对中国剩余定理的证明就错误了。

我们退而求其次，考虑如何合并两个同余方程，下面给出两个例子：

Exempli Gratia 1 $m_i$ 之间互质时

考虑合并以下两个同余式：

我们可以这样做：

假设有一组针对①成立的通解 $x=6k+4,k\in\mathbb{Z}$，如果 $x$ 要满足②，那么我们可以得到：

然后我们砍掉 $5k$（因为是$5$的倍数），再利用同加性得到：

再将 $k$ 带回①式中得到：

再转换成同余式又可以得到：

以上合并的结果就是 $x\equiv28(mod \ 30)$

Exempli Gratia 2 $m_i$之间不互质时

考虑合并以下两个同余式：

再使用 $EG1$ 中的办法可以得到：

用同加性质可以得到：

最后可以转移出 $k=3s+2,s\in\mathbb{Z}$，进一步得出：

最终合并的结果即为：$x\equiv10(mod \ 12)$

Exempli Gratia 3 无解

考虑合并以下两个同余式：

合并不起来，无解。

同余方程合并的性质
  • 新方程与原方程具有同样的形式。
  • 新方程的模数是原来方程的 $lcm$。
  • 可能会无解。
    关于为什么新的模数是 $lcm$，刚才的合并已经给出了隐涩的证明。
    有一个更好的理解思路：想象两个模数为两个周期，这两个周期重叠时的最小正整数为他们的 $lcm$，所以新的模数是 $lcm$ 是正确的。
二项同余方程的通解

通过刚才的铺垫，我们可以对于任意的一组线性同余方程：

我们可以得出一组等价的：$x=k_1m_1+a_1=k_2m_2+a_2,k\in\mathbb{Z}$

再移项得到：$k_1m_1-k_2m_2=a_2-a_1$

仔细一看，发现未知量好像只有 $k_1$ 和 $k_2$，那么这不就是个不定方程吗！

于是可以使用裴蜀定理判定是否有解（$gcd(m_1,m_2)|(a_2-a_1)$）

那么我们按照$exgcd$的套路构造出一组 $k_1,k_2$，设 $d=gcd(m_1,m_2)$，$p_1=\frac{m_1}{d}$，$p_2=\frac{m2}{d}$，刚才的式子可以转换成：

考虑 $-k_2<0$，我们需要进行转换，求出以下方程的解：

接下来可以转换为一组$k_1$与$k_2$的特解：

于是就可以构造出 $x$ 的一组解 $x=a_1+k_1m_1=a_1+\lambda m_1 \frac{a_2-a_1}{d}$（也可以使用 $k_2$ 和 $\mu$ 构造）

那么我们再根据特解提出一个引理：

根据一个特解 $x^*$，对于

对通解换种说话，也可以等价于：

我们提炼以下这里面的信息：该方程在 $[0,lcm(m_1,m_2)]$ 有且仅有一个解（即最小整数解）并且在接下来每个长度为 $lcm(m_1,m_2)$ 的区间内都只有一个解。

对于证明刚才的通解，我们可以考虑下面的问题：

针对方程

我们可以假设 $x \ge y$，然后就可以发现

也就可以得出 $lcm(m_1,m_2)|(x-y)$。

这时候思考一下，$x,y\le lcm(m_1,m_2)$，所以 $x-y<lcm(m_1,m_2)$，但是如果要令 $lcm(m_1,m_2)|(x-y)$，那么就必须要让 $x=y$。

刚才的证明同时证明了该通解的周期和在周期内的唯一性，所以通解成立。

求解

对于 $m_i$ 之间不互质的同余方程组的解法已经呼之欲出了：考虑从上到下合并每个同余式，用裴蜀定理检验最终求解。

但是证明和实现之间总是有千山万水的距离，让我们再把理论和算法拉近一点，如何合并？

我们根据之前的通解假设已经构造出前 $k-1$ 个方程的通解

那么对于加入了第 $k$ 个方程的通解，就是要求解一个新的 $t$，使得：

我们可以考虑移项得到一个不定方程：

每次使用裴蜀定理检测再使用 $exgcd$ 求解新的同余方程是否有解即可。

小$tip$:$EXCRT$ 可以解决中国剩余定理的问题，所以推荐学完 $EXCRT$ 就可以忘掉中国剩余定理了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//EXCRT luogu P4777
#define MAXN 100050
#define ll long long
ll W[MAXN],B[MAXN],k;
inline ll ksc(ll a,ll b, ll mod){
	ll ans=0;
	while(b){
		if(b&1)ans=(ans+a)%mod;
		a=(a+a)%mod;
		b>>=1;
	}
	return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(!b){x=1,y=0;return a;}
	ll gcd=exgcd(b,a%b,x,y);
	int temp=x;x=y;y=temp-(a/b)*y;
	return gcd;
}
int main(){
	cin>>k;
	for(int i=1;i<=k;++i)cin>>W[i]>>B[i];
	ll ans=B[1],M=W[1],t,y;
	for(int i=2;i<=k;++i){
		ll a=M,b=W[i],c=(B[i]-ans%b+b)%b;
		ll gcd=exgcd(a,b,t,y);
		//构造出 M*t+mi*y≡mi-Ans(mod mi)的式子
		ans+=ksc(t,c/gcd,b)*M;//求出线性同余方程的一组解
		M*=b/gcd;//更新M为新的lcm
		ans=(ans%M+M)%M;
	}
	cout<<ans<<endl;
}

致谢

  • 感谢洛谷的《深入浅出进阶篇》中对 $CRT$ 部分的证明对本篇文章的启发。
  • 感谢东营市第一中学的郑华松教练提供了 $EXCRT$ 中线性同余式合并的思路。
  • 感谢阮行止、$niiick$ 的博客对本篇文章 $EXCRT$ 部分的启发。