拓展中国剩余定理（exCRT）

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

可以发现一个问题：exCRT 的前置知识不包括 CRT，那是因为，这两者关系不大。

exCRT 与 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}$

但是 exCRT 不需要 $b_i$ 两两互质这个前提条件。

它的思想是数学归纳法，具体方法是这样的：

方法

如果只有一个方程，那么 $x = a_1$。

如果不止一个方程：

假设已经求出了前 $i - 1$ 个方程的一个解 $x$。

记 $m$ 为 $\operatorname{lcm}(b_1, b_2, b_3, \dots, b_{i - 1})$，则 $x + t \times m$ 是前 $i - 1$ 个方程的通解。

求出一个整数 $t$，使得 $x + t \times m \equiv a_i \pmod{b_i}$，若有解，则 $x + t \times m$ 就是前 $i$ 个方程的一个解。

$x + t \times m \equiv a_i \pmod{b_i}$ 应该怎么求呢？

我们把它变一下形：

$\begin{aligned} x + t \times m & \equiv a_i \pmod{b_i}\\ x + t \times m & = a_i + k \times b_i\\ t \times m + k \times (-b_i) & = a_i - x\\ t \times m + (-k) \times b_i & = a_i - x \end{aligned}$

设 $k' = -k$，则 $t \times m + k' \times b_i = a_i - x$。

现在，如果 $\gcd(m, b_i) | a_i - x$ 不成立，那么无解；否则，用拓欧求出 $t \times m + k' \times b_i = \gcd(b_i, m)$，再将 $t$ 和 $k$ 都乘上 $\dfrac{a_i - x}{\gcd(m, b_i)}$ 即可。

代码实现：

注意：exCRT 非常容易爆 long long！

#include <algorithm>
#include <cstdio>
#include <cmath>
#define ll __int128

using namespace std;

ll gcd(ll a, ll b){
	if (!b) return a;
	return gcd(b, a % b);
}
inline ll lcm(ll a, ll b){
	return a * b / gcd(a, b);
}
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;
}
int n;
ll a[100001], b[100001], A, ans, d, m, k, x, y;
int main(){
	scanf("%d", &n);
	for (int i = 1;i <= n;i ++) scanf("%lld%lld", &b[i], &a[i]);
	ans = a[1];
	m = b[1];
	for (int i = 2;i <= n;i ++){
		A = ((a[i] - ans) % b[i] + b[i]) % b[i];
		d = exgcd(m, b[i], x, y);
		if (A % d != 0){
			printf("-1");
			return 0;
		}
		k = x * (A / d) % b[i];
		ans += k * m;
		m = lcm(m, b[i]);
		ans = (ans % m + m) % m;
	}
	printf("%lld", (long long)ans);
}