参考
中国剩余定理:
参考博客
中国剩余定理介绍
在《孙子算经》中有这样一个问题:“今有物不知其数,三三数之剩二(除以3 余2),五五数之剩三(除以5 余3),七七数之剩二(除以7 余2),问物几何?”这个问题称为“孙子问题”,该问题的一般解法国际上称为“中国剩余定理”。
具体解法分三步:
-
找出三个数,从3和5的公倍数中找出被7除余1(
≡
≡
1 mod 7)的最小数15
从3和7的公倍数中找出被5除余1(
≡
≡
1 mod 5)的最小数21
最后从5和7中找出除3余1(
≡
≡
1 mod 3)的最小数70.
-
用15乘2(2为最终结果除以7的余数),21乘3(3为最终结果除以5的余数),70乘2(2为最终结果除以3的余数),把三个乘积相加(15*2+21*3+70*2)得到233.
- 用233除以3,5,7的最小公倍数105,得到余数23,即233%105=23,这个23就是符合条件的最小数
如此简单的方法,背后有什么基本的数学依据呢?
下面细细道来:
中国剩余定理分析
我们将问题拆分成几个简单的小问题,从零开始,揣测古人是如何推导出这个解法的。
首先我们假设
n1
n
1
是满足除以3余2的一个数(即
n1≡2(mod3)
n
1
≡
2
(
m
o
d
3
)
),比如2,5,8等等,也就满足3*k+2的任意一个数。同样我们假设
n2
n
2
是满足除以5余3的一个数(即
n2≡3(mod5)
n
2
≡
3
(
m
o
d
5
)
),
n3
n
3
是满足除以7余2的一个数(即
n3≡2(mod7)
n
3
≡
2
(
m
o
d
7
)
)。
有了前面的假设,我们先从
n1
n
1
的角度出发,已知
n1
n
1
满足除以3余2,那么我们想,能不能使
n1+n2
n
1
+
n
2
的和仍然满足除以3余2?进而使得
n1+n2+n3
n
1
+
n
2
+
n
3
的和仍然满足除以3余2?
这就涉及到一个基本数学同余定理(a):
如果有a % b = c,则有(a + kb)%b = c(k为非零整数)
或者写成
a≡c
a
≡
c
(mod b),则有
a+kb≡c
a
+
k
b
≡
c
(mod b)(k为非零整数)
(这个定理非常简单也易于理解不再过多解释(若不懂可查看相关同余的知识))
以此为依据,如果
n2
n
2
是3的倍数,那么
n1+n2
n
1
+
n
2
就能满足除以3余2,同理如果
n3
n
3
也是3的倍数,那么
n1+n2+n3
n
1
+
n
2
+
n
3
仍然满足除以3余2.同理我们从
n2,n3
n
2
,
n
3
的角度考虑得到以下三点:
1. 为使
n1+n2+n3
n
1
+
n
2
+
n
3
的和满足除以3 余2,
n2
n
2
和
n3
n
3
必须是3 的倍数。
2. 为使
n1+n2+n3
n
1
+
n
2
+
n
3
的和满足除以5 余3,
n1
n
1
和
n3
n
3
必须是5 的倍数。
3. 为使
n1+n2+n3
n
1
+
n
2
+
n
3
的和满足除以7 余2,
n1
n
1
和
n2
n
2
必须是7 的倍数
↓
↓
1.
n1
n
1
除以3 余2,且是5 和7 的公倍数。
2.
n2
n
2
除以5 余3,且是3 和7 的公倍数。
3.
n3
n
3
除以7 余2,且是3 和5 的公倍数。
↓
↓
孙子问题解法的本质是
1. 从5 和7 的公倍数中找一个除以3 余2 的数
n1
n
1
2. 从3 和7的公倍数中找一个除以5 余3 的数
n2
n
2
3. 从3 和5 的公倍数中找一个除以7 余2 的数
n3
n
3
再将 三个数相加得到解。
在求解过程中又用了一个小技巧,相信大家在刚才的例子中已经发现,以n1 为例,并非从5 和7 的公 倍数中直接找一个除以3 余2 的数,而是先找一个除以3 余1 的数,再乘以2。这是为什么?
下面引入另一个数学同余定理(b)
如果a%b=c,那么(a*k)%b = (a%b+a%b+…a%b)%b = (c+c+c+…+c)%b = k*c%b(k>0)
也就是说,如果一个除法的余数为c,那么被除数乘k倍,余数也跟着变成k倍,反之也成立。
最后,我们还要清楚一点,
n1+n2+n3
n
1
+
n
2
+
n
3
只是问题的一个解,并不是最小的解。实际上
n1+n2+n3
n
1
+
n
2
+
n
3
+
n⋅lcm
n
⋅
l
c
m
都是解。
如何得到最小解?我们只需要从中最大限度的减掉掉3,5,7 的公倍数105 即可。道理就是前面讲过的定理“如果a%b=c,则有(a-kb)%b=c”。(
n1+n2+n3
n
1
+
n
2
+
n
3
)%105 就是最终的最小解。
总结
经过分析发现,中国剩余定理的孙子解法并没有什么高深的技巧,就是以下两个基本数学
定理的灵活运用:
如果 a%b=c , 则有 (a+kb)%b=c (k 为非零整数)。
如果 a%b=c,那么 (a*k)%b=kc%b (k 为大于零的整数)。
推广到一般情况
例如下面的一元线性同余方程组:
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
x ≡ a3 (mod m3)
… …
x ≡ an (mod mn)
假设整数
m1,m2,m3...mn
m
1
,
m
2
,
m
3
.
.
.
m
n
两两互质,
m=m1⋅m2...mn
m
=
m
1
⋅
m
2
.
.
.
m
n
则对于任意整数
a1,a2,a3...an
a
1
,
a
2
,
a
3
.
.
.
a
n
,x有解
求解x的过程:
(为了便于叙述,下面用同余的写法)
x=⟮
x
=
⟮
(
≡a1
≡
a
1
(mod
m1
m
1
) 并且是
m2,m3..mn
m
2
,
m
3
.
.
m
n
的公倍数的数)+…+(
≡aj
≡
a
j
(mod
mj
m
j
)并且是
m1...mj−1,mj+1...mn
m
1
.
.
.
m
j
−
1
,
m
j
+
1
.
.
.
m
n
的公倍数的数)+…+(
≡an
≡
a
n
(mod
mn
m
n
)并且是
m1...mn−1
m
1
.
.
.
m
n
−
1
的公倍数)
⟯
⟯
%
lcm(m1...mn)
l
c
m
(
m
1
.
.
.
m
n
)
问题转换成:找到
≡aj
≡
a
j
(mod
mj
m
j
)的
m1...mj−1,mj+1...mn
m
1
.
.
.
m
j
−
1
,
m
j
+
1
.
.
.
m
n
的公倍数
↓
↓
我们可以先求
≡1
≡
1
(mod
mj
m
j
)的
m1...mj−1,mj+1...mn
m
1
.
.
.
m
j
−
1
,
m
j
+
1
.
.
.
m
n
的公倍数
Nj
N
j
,然后
Nj∗aj
N
j
∗
a
j
即可
↓
↓
问题转换成:求
Nj
N
j
因为
Nj
N
j
是
m1...mj−1,mj+1...mn
m
1
.
.
.
m
j
−
1
,
m
j
+
1
.
.
.
m
n
的公倍数,我们知道
m1...mj−1,mj+1...mn
m
1
.
.
.
m
j
−
1
,
m
j
+
1
.
.
.
m
n
的最小公倍数
Mj=mmj
M
j
=
m
m
j
(因为
m1...mn
m
1
.
.
.
m
n
互质),所以
Nj
N
j
可以表示成
Nj
N
j
=
Mj∗R
M
j
∗
R
↓
↓
问题再次转换为:求R,使得
MjR≡1
M
j
R
≡
1
(mod
mj
m
j
),发现R就是
Mj
M
j
的逆元,我们要求
Mj
M
j
的乘法逆元
↓
↓
求乘法逆元运用扩展欧几里得算法:
MjR+mjy=1
M
j
R
+
m
j
y
=
1
,变量是R和y,调用ex_gcd(
Mj,mj,R,y
M
j
,
m
j
,
R
,
y
)
↓
↓
最终
x=∑(Rj∗Mj)∗aj
x
=
∑
(
R
j
∗
M
j
)
∗
a
j
((
Rj∗Mj
R
j
∗
M
j
)是
Nj
N
j
即取模为1的…,
aj
a
j
就是那个余数一相乘得到取模为
aj
a
j
的…)
代码:
//扩展欧几里得模板
int ex_gcd(int a,int b,int &x,int &y){
int d;
if(b == 0){
x = 1;
y = 0;
return a;
}
d = ex_gcd(b,a%b,y,x);
y -= a / b * x;
return d;
}
int Chinese_Remainder(int a[],int prime[],int len){
int i,d,R,y,M,m = 1,sum = 0;
//计算所有除数的积,也就是所有除数的最小公倍数m
for(i = 0; i < len; i++)
m *= prime[i];
//计算符合所有条件的数
for(i = 0; i < len; i++){
M = m / prime[i];//计算除去本身的所有除数的积M
d = ex_gcd(M,prime[i],R,y);
sum = (sum + R * M * a[i]) % m;
}
return (m + sum % m) % m;//满足所有方程的最小解
}
m1...mn
m
1
.
.
.
m
n
不互质的情形:合并方程:
x≡a1
x
≡
a
1
(mod
m1
m
1
)
x≡a2
x
≡
a
2
(mod
m2
m
2
)
↓
↓
x=m1x1+a1
x
=
m
1
x
1
+
a
1
x=m2x2+a2
x
=
m
2
x
2
+
a
2
↓
↓
m1x1+a1=m2x2+a2
m
1
x
1
+
a
1
=
m
2
x
2
+
a
2
↓
↓
m1x1=(a2−a1)+m2x2
m
1
x
1
=
(
a
2
−
a
1
)
+
m
2
x
2
↓
↓
m1x1≡(a2−a1)
m
1
x
1
≡
(
a
2
−
a
1
)
(mod
m2
m
2
)
显然,该同余式要想有解,根据同余式定理,必须有
gcd(m1,m2)|(a2−a1)
g
c
d
(
m
1
,
m
2
)
|
(
a
2
−
a
1
)
设
gcd(m1,m2)=d
g
c
d
(
m
1
,
m
2
)
=
d
,
(a2−a1)=c
(
a
2
−
a
1
)
=
c
则式子变成
m1x1≡c
m
1
x
1
≡
c
(mod
m2
m
2
)
↓
↓
根据同余式定理求解方法,我们先解
m1k1+m2k2=d
m
1
k
1
+
m
2
k
2
=
d
解出
k1
k
1
后在求出最小正整数解
x1
x
1
↓
↓
m1x1d≡cd(modm2d)
m
1
x
1
d
≡
c
d
(
m
o
d
m
2
d
)
x1≡cd⋅(m1d)−1(modm2d)
x
1
≡
c
d
⋅
(
m
1
d
)
−
1
(
m
o
d
m
2
d
)
令
X=cd⋅(m1d)−1
X
=
c
d
⋅
(
m
1
d
)
−
1
则
x1≡X(modm2d)
x
1
≡
X
(
m
o
d
m
2
d
)
x1=m2dy+X
x
1
=
m
2
d
y
+
X
根据
x=m1x1+a1
x
=
m
1
x
1
+
a
1
,代入得到
x=m1m2dy+m1X+a1
x
=
m
1
m
2
d
y
+
m
1
X
+
a
1
即:
x≡(m1X+a1)(modm1m2d)
x
≡
(
m
1
X
+
a
1
)
(
m
o
d
m
1
m
2
d
)
最终我们将两个同余式合并成了一个都变成了
x≡a
x
≡
a
(mod n)的形式,所以不断合并,最终的a和x同余就是我们所求的x值。
代码怎么写呢?
其实答案就在上面推导过程中
我们根据两个同余式
运用扩展欧几里得解同余式
m1x1≡(a2−a1)
m
1
x
1
≡
(
a
2
−
a
1
)
(mod
m2
m
2
)
解出
x1≡X(modm2d)
x
1
≡
X
(
m
o
d
m
2
d
)
而新的同余式是
x≡(m1X+a1)(modm1m2d)
x
≡
(
m
1
X
+
a
1
)
(
m
o
d
m
1
m
2
d
)
这样我们就可以求出新的同余式的a值和m值了,然后不断循环求解得到最终的a值
code:
//有时候可能会用到lcm来求解多组解,因为你求出来的是最小解,所以你就可以通过不断加lcm求解多组解
int lcm;
int china2(int num){//不互质的中国剩余定理
int m1=m[0],a1=a[0],m2,a2,k1,k2,x0,gcd,c;//这里的x0相当于推导过程中的x1
lcm=m[0];
for(int i=1;i<num;i++){
m2=m[i],a2=a[i];
c=a2-a1;
gcd=exgcd(m1,m2,k1,k2);//解得:n1*k1+n2*k2=gcd(n1,n2)
lcm=lcm*m[i]/Gcd(lcm,m[i]);//通过这个循环求解出所有mod的最大公约数
if(c%gcd){
flag=1;//!!!!!!china也可以求解出为0的值,所以为0不一定就是无解,所以你要通过flag来判断是否无解。
return 0;//无解
}
x0=c/gcd*k1;//n1*x0+n2*(c/gcd*k2)=c PS:k1/gcd*c错误!
int t=m2/gcd;
x0=(x0%t+t)%t;//求n1*x0+n2*y=c的x0的最小解
a1+=m1*x0;
m1=m2/gcd*m1;
}
return a1;
}
若内容有误欢迎指正