有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五使得知

——《孙子算经》

它可以做什么？

中国剩余定理可以用于解决形如以下形式的线性同余方程组

(X){x1≡b1(modm1)x2≡b2(modm2)…xn≡bn(modmn)(X)\left\{\begin{matrix}x_1\equiv b_1\pmod{m_1}\\x_2\equiv b_2\pmod{m_2}\\\ldots\\x_n\equiv b_n\pmod{m_n}\end{matrix}\right.

其中m1,m2,m3,…,mnm_1,m_2,m_3,\ldots,m_n两两互质

它是怎么做的？

中国剩余定理利用构造法给出了一组解，构造方法如下：

设M=∏i=1nmiM=\prod_{i=1}^nm_i，并设Mi=M/miM_i=M/m_i，即Mi=∏j=1,j≠inmjM_i=\prod_{j=1,j\neq i}^nm_j
设ti=Mi−1t_i=M_i^{-1}为MiM_i模mim_i意义下的逆元，那么同余方程组(X)(X)的通解可以表示为以下形式：

x=∑i=1nbiMiti+kM,M∈Zx=\sum_{i=1}^nb_iM_it_i+kM,M\in\mathbb{Z}

在模MM意义下，方程组的解为：

x=(∑i=1nbiMiti)(modM)x=(\sum_{i=1}^nb_iM_it_i)\pmod{M}

为什么是正确的？

证明如下:

由于m1,m2,m3,…,mnm_1,m_2,m_3,\ldots,m_n两两互质，因此有gcd⁡(Mi,mi)=1\gcd(M_i,m_i)=1，所以存在tit_i满足Miti=1(modmi)M_it_i=1\pmod{m_i}

于是有：biMiti≡bi∗1≡bi(modmi)b_iM_it_i\equiv b_i*1\equiv b_i\pmod {m_i}

且对于∀j∈{1,2,3,…,n},j≠i\forall j\in\{1,2,3,\ldots,n\},j\neq i，有biMiti≡0(modmj)b_iM_it_i\equiv0\pmod{m_j}

那么对于∀i∈{1,2,3,…,n}\forall i\in\{1,2,3,\ldots,n\}，x=∑i=1nbiMitix=\sum_{i=1}^nb_iM_it_i满足：

x≡biMiti+∑j=1,j≠inbjMjtj(modmi)≡bi∗1+∑j=1,j≠in0(modmi)≡bi(modmi)x\equiv b_iM_it_i+\sum_{j=1,j\neq i}^nb_jM_jt_j\pmod{m_i}\equiv b_i*1+\sum_{j=1,j\neq i}^n0\pmod{m_i}\equiv b_i\pmod{m_i}

由此可以证明xx是同余方程组(X)(X)的一个解

另外，若x1,x2x_1,x_2都是方程组(X)(X)的解，那么

对于∀i∈{1,2,3,…,n},x1−x2≡0(modmi)\forall i\in\{1,2,3,\ldots,n\},x_1-x_2\equiv0\pmod{m_i}

而m1,m2,m3,…,mnm_1,m_2,m_3,\ldots,m_n两两互质，所以M∣(x1−x2)M|(x_1-x_2)，这说明方程组(X)(X)的任意两个解之间相差kM,k∈ZkM,k\in\mathbb{Z}

那么方程组的所有整数解的形式即为：

x=∑i=1nbiMiti+kM,k∈Zx=\sum_{i=1}^nb_iM_it_i+kM,k\in\mathbb{Z}

Code

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#define maxn 105
using namespace std;

int n;
int b[maxn],m[maxn],lcm=1,M[maxn],t[maxn];

int exgcd(int a,int p,int &x,int &y)
{
	if(!p)
	{
		x=1;
		y=0;
		return a;
	}
	int xx,yy,k;
	k=exgcd(p,a%p,xx,yy);
	x=yy;
	y=xx-a/p*yy;
	return k;
}

int main()
{
	int ans=0;
	scanf("%d",&n);
	register int i;
	for(i=1;i<=n;++i)
	{
		scanf("%d%d",&b[i],&m[i]);
		lcm*=m[i];
	}
	for(i=1;i<=n;++i)
	{
		int x,y;
		M[i]=lcm/m[i];
		exgcd(M[i],m[i],x,y);
		ans=(ans+b[i]*M[i]*x)%lcm;
	}
	printf("%d",ans);
	return 0;
}

例题

UVA756 Biorhythms

Description

输入包含若干个测试点，以四个 −1-1 结束。

每一个测试点输入四个整数 pp, ee, ii 和 dd。求最小的 xx，使得 x>dx>d 并且

{x≡p(mod23)x≡e(mod28)x≡i(mod33)\left\{\begin{matrix}x\equiv p\pmod{23}\\x\equiv e\pmod{28}\\x\equiv i\pmod{33}\end{matrix}\right.

输出x−dx-d的值

输出请按照如下格式：

1
Case 1: the next triple peak occurs in 1234 days.

Solution

中国剩余定理裸题，直接套用即可

Code

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
50
51
52
53
54
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
using namespace std;
typedef long long ll;

int b[4],m[4]={0,23,28,33},M[4]={0,924,759,644},t[4];
int lcm=21252;//23*28*33

void exgcd(int a,int b,int &x,int &y)
{
	if(!b)
	{
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}

void Pre()
{
	int y;
	for(int i=1;i<=3;++i)
	{
		exgcd(M[i],m[i],t[i],y);
		t[i]=(t[i]+m[i])%m[i];
	}
}

int main()
{
	Pre();
	int cas=0,d;
	while(1)
	{
		for(int i=1;i<=3;++i)
			scanf("%d",&b[i]);
		scanf("%d",&d);
		if(b[1]==-1)
			break;
		int ans=0;
		for(int i=1;i<=3;++i)
			ans=(ans+b[i]*M[i]*t[i]%lcm)%lcm;
		ans=(ans-d+lcm)%lcm;
		if(ans==0)
			ans=lcm;
		printf("Case %d: the next triple peak occurs in %d days.\n",++cas,ans);
	}
	return 0;
}

部分内容来源：
孙子定理_百度百科
《信息学奥赛之数学一本通》林厚从 著