题解：P4777 【模板】扩展中国剩余定理（EXCRT）

# 扩展中国剩余定理 exCRT
## 算法介绍

要想学会扩展中国剩余定理，要先学会 [exgcd](https://www.luogu.com.cn/problem/P5656)，至于中国剩余定理，这并不重要。

中国剩余定理给了你一个一元线性同余方程组：
$$\begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x\equiv b_n\pmod{a_n}\end{cases}$$
让你求出 $x$ 的最小非负整数解，在中国剩余定理中，给了你 $a_1 \sim a_n$ 互质的条件，但扩展中国剩余定理没有，我们考虑如何解决。

注意到，我们难以直接算出 $x$ 的最小非负整数解，所以我们考虑把这些同余方程组两两合并，我们考虑如何求出如下同余方程组：
$$\begin{cases}x\equiv x_1\pmod{y_1}\\x\equiv x_2\pmod{y_2}\\\end{cases}$$
扩展中国剩余定理告诉我们，它们可以合并成一个同余方程：
$$x\equiv x_1 - y_1 \times a\pmod{\operatorname{lcm}(y_1,y_2)}$$
然后以此类推，两两合并，直到合并成一个方程，我们就求出了原方程组的解。接下来我们考虑如何证明它。
## 正确性证明
把同余方程写成等式：
$$x_1 = y_1 \times k_1 + x \\ x_2 = y_2 \times k_2 + x $$
可以得出：
$$x_1 - y_1 \times k_1 = x_2 - y_2 \times k_2$$
整理式子：
$$y_1 \times k_1 - y_2 \times k_2 = x_1 - x_2$$
这样我们就把它写成了二元一次方程组，于是我们可以用 exgcd 求出 $y_1 \times k_1 - y_2 \times k_2 = \gcd (y_1,y_2)$ 的解，我们令其为 $a$ 与 $b$。

那么原二元一次方程组的解为：
$$k_1 = a + \frac{y_2}{\gcd (y_1,y_2)} \times k \\ k_2 = b - \frac{y_1}{\gcd (y_1,y_2)} \times k$$
根据前文，我们知道：
$$x = x_1 - y_1 \times (a + \frac{y_2}{\gcd (y_1,y_2)} \times k)$$
展开一下：
$$x = x_1 - y_1 \times a + y_1 \times \frac{y_2}{\gcd (y_1,y_2)} \times k \\ x = x_1 - y_1 \times a + \frac{y_1 \times y_2}{\gcd (y_1,y_2)} \times k$$
我们都知道，$a \times b = \gcd (a,b) \times \operatorname{lcm}(a,b)$，那我们的式子可以改写成：
$$x = x_1 - y_1 \times a + \operatorname{lcm}(y_1,y_2) \times k$$
然后我们把它再次转换成同余方程，把我们设的 $k$ 换成同余方程：
$$x\equiv x_1 - y_1 \times a\pmod{\operatorname{lcm}(y_1,y_2)}$$
这样，我们就证明完了我们上面给出的那个式子。

然后，我们就可以写代码了。

## 代码实现

注意计算过程可能会爆 long long，记得开 int128。

```cpp
#include<bits/stdc++.h>
#define int __int128//计算过程可能会爆 long long
#define code using
#define by namespace
#define dong0717 std;
code by dong0717
int x,y;
int exgcd(int a,int b){//exgcd模板
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	int d=exgcd(b,a%b);
	int t=x;
	x=y;
	y=t-a/b*y;
	return d;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	long long n;
	cin>>n;
	int a1=1,b1=0;
	for(int i=1;i<=n;i++){
	    long long a2,b2;
		cin>>a2>>b2;
		int d=exgcd(a1,(__int128)a2);
		x=(b1-b2)/d*x;
		b1-=a1*x;
		a1=a2/d*a1;
		b1=(b1%a1+a1)%a1;
	}
	cout<<(long long)((b1%a1+a1)%a1);
	return 0;
}
```

正在渲染内容...