中国剩余定理

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

答案：23

口诀：三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知

其实原问题就是求解以下的同余方程组
$$\{\begin{array}{r}x\equiv 2(mod3)\\ x\equiv 3(mod5)\\ x\equiv 2(mod7)\end{array}$$
而 $23=(2\times 70+3\times 21+2\times 15)mod(3\times 5\times 7)$，那$70，21，15$是怎么求得的呢，通过以下三步：

• $70$实际上是$5$和$7$的公倍数中模$3$余$1$的最小的那个数，$x\equiv 1(mod3)$，其中$x=35k$
• $21$实际上是$3$和$7$的公倍数中模$5$余$1$的最小的那个数，$x\equiv 1(mod5)$，其中$x=21k$
• $15$实际上是$3$和$5$的公倍数中模$7$余$1$的最小的那个数，$x\equiv 1(mod7)$，其中$x=15k$

其中有什么原理呢？

首先假设$x_1$是$x\equiv 2(mod3)$的解，$x_2$是$x\equiv 3(mod5)$的解，$x_3$是$x\equiv 2(mod7)$的解

那么能否进一步满足，$x_1+x_2$模$3$余$2$也成立呢？只要满足**$x_2$是$3$的倍数就可以，同理要使得$x_1+x_3$模$3$余$2$也成立，那么$x_3$也得是$3$的倍数**，这是从$x_1$的角度出发

来看$x_2$，$x_2$满足模$5$余$3$成立。为了使得$x_1+x_2$也满足模$5$余$3$成立，那么$x_1$必须是$5$的倍数，同理，$x_3$也要是$5$的倍数，才能满足$x_2+x_3$模$5$余$3$成立。

最后是$x_3$。同理**$x_1，x_2$也必须是$7$的倍数**。弄清楚了这些条件

那么$x_1+x_2+x_3$就是最终的一个答案了。总的来说这$3$个数要满足

• $x_1$模$3$余数是$2$，同时$x_1$是$5$和$7$的一个公倍数
• $x_2$模$5$余数是$3$，同时$x_2$是$3$和$7$的一个公倍数
• $x_3$模$7$余数是$2$，同时$x_3$是$3$和$5$的一个公倍数

需要注意的是，$x_1+x_2+x_3$只是其中一个解，并不是最小的解。要明白如果$t$是上述同余方程组的解那么$t+105k$也是方程组的解。$105$是$3，5，7$的最小公倍数

求解的时候，可以使用扩展欧几里德算法，将$x_1$模$3$余数是$2$，变成$x_1$模$3$余数是$1$，将答案乘以$2$即可，相当于求$x1-3k=1$

例题：

给定 $n$ 组非负整数 $a_i,b_i$ ，求解关于 $x$ 的方程组的最小非负整数解。(其中$a_i$两两互质)
$$\{\begin{array}{r}x\equiv b_1(mod{a}_1)\\ x\equiv b_2(mod{a}_2)\\ ................\\ x\equiv b_n(mod{a}_n)\end{array}$$
输入

输入第一行包含整数 $n$。

接下来 $n$ 行，每行两个非负整数 $a_i,b_i$。

输出

输出一行，为满足条件的最小非负整数 $x$。

输入样例

3
2 1
3 2
5 3

输出样例

23

代码

#include <cstdio>
#include <iostream>
#define N 100005
#define ll long long
using namespace std;

ll a[N], b[N], M = 1;
int n;

void ex_gcd (ll a, ll b, ll &x, ll & y) { //扩展欧几里德
	if (!b) {
		x = 1, y = 0;
		return ;
	}
	ex_gcd(b, a%b, x, y);
	ll t = x;
	x = y;
	y = t - a / b * y;
}

ll CRT () {
	ll ans = 0, x, y, g;
	for (int i = 1; i <= n; i++)
		M *= a[i];
	for (int i = 1; i <= n; i++) {
		ex_gcd (M / a[i], a[i], x, y);
		ans = (ans + x * (M / a[i]) * b[i]) % M; 
	}
	return (ans + M) % M;
}

int main () {
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++) 
		scanf ("%lld %lld", &a[i], &b[i]);
	printf("%lld\n", CRT ());
	return 0;
}