中国剩余定理（CRT）

前置知识：拓展欧几里得算法

当 $b_i$ 两两互质，CRT 可以求解这样的同余方程组：

$\begin{cases} x \equiv a_1 \pmod{b_1}\\ x \equiv a_2 \pmod{b_2}\\ x \equiv a_3 \pmod{b_3}\\ \vdots\\ x \equiv a_n \pmod{b_n}\\ \end{cases}$

显然，如果有解，肯定是模 $\operatorname{lcm}(b_1, b_2, \dots, b_n)$ 意义下的解。

如果 $b_i$ 两两互质，那么 CRT 可以给出模 $\prod_{i = 1}^n b_i$ 的意义下的唯一解的构造方式。

构造

设 $M$ 为 $\prod_{i = 1}^n b_i$，$m_i$ 为 $\dfrac{M}{b_i}$。

因为 $b_i$ 两两互质，所以 $\gcd(b_i, m_i) = 1$。

对于每一个 $i$，解出二元一次不定方程 $u_im_i + v_ib_i = \gcd(b_i, m_i)$。

解 $x$ 即为 $\sum_{i = 1}^n a_iu_im_i$。

证明

我们来验证一下构造的正确性。

对于每个 $i$：

$\begin{aligned} x & \equiv \sum_{i = 1}^n a_iu_im_i\\ & \equiv a_iu_im_i\\ & \equiv a_i(1 - v_ib_i)\\ & \equiv a_i \end{aligned}$

对于每个 $i$，都使用一次拓欧，时间复杂度为 $O(\sum \log b_i)$。

代码实现：

#include <cstdio>
#define ll long long

int n, a[11], b[11];
ll exgcd(ll a, ll b, ll& x, ll& y){
	if (!b){
		x = 1, y = 0;
		return a;
	}
	ll ret = exgcd(b, a % b, x, y);
	ll t = x;
	x = y;
	y = t - (a / b) * y;
	return ret;
}
ll M = 1, Mi[11], x, y, ans;
int main(){
	scanf("%d", &n);
	for (int i = 1;i <= n;i ++) scanf("%d%d", &a[i], &b[i]), M *= a[i];
	for (int i = 1;i <= n;i ++){
		Mi[i] = M / a[i];
		ll x, y;
		exgcd(Mi[i], a[i], x, y);
		ans += b[i] * Mi[i] * (x < 0 ? x + a[i] : x);
	}
	printf("%lld", ans % M);
}