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

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


· 引入

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

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


· 扩展中国剩余定理

- 前置

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

- 推导

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

根据同余的定义,我们可以写出:

所以有 $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$ ;
则有:

那么就可以得到 $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}$;则有:

通过欧几里得定理得到 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*MM=M*m[i]/g(也就是M和m[i]的最小公倍数);
使 R 的绝对值尽可能小:R=R%M

- 伪代码

1
2
3
4
5
6
7
8
9
10
11
12
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 为参考)

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*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 ,欢迎提问~

0%