## [扩展中国剩余定理](https://www.luogu.com.cn/problem/P4777)

### 一、[题目描述]

给定  $k$ 组非负整数  $m_i, a_i$ ，求解关于  $x$ 的方程组的最小非负整数解。
$$\begin{cases} x \equiv a_1\ ({\rm mod}\ m_1) \\ x\equiv a_2\ ({\rm mod}\ m_2) \\ ... \\ x \equiv a_k\ ({\rm mod}\ m_k)\end{cases}$$

### 二、推导过程
首先，我们假定已经找到了前$k-1$个方程组的解：$ans+iM$,其中$\displaystyle M=\prod_{i=1}^{k-1} m_i  $


那么我们现在需要找到一个非负整数，满足$ans+tM \equiv a_k (mod \ m_k)$，移项得
$tM \equiv a_k-ans(mod \ m_k)$

我们发现，这个形式与扩展欧几里得($exgcd$)的变形$ax \equiv c(mod \ b)$ 相同，于是令 

$$
\large \left\{\begin{matrix}
A = M & \\ 
B = m_k & \\
C=|a_k-ans| & \\ 
X=t
\end{matrix}  
 \right.
$$

那么问题就转化为我们就要求不定方程$AX \equiv C(mod \ B)$ 的解。 

而$exgcd(A,B,X,Y)$可以得到满足$AX+BY=gcd(A,B)$ 的一组解，将此式放在模$B$ 的意义下，就是$AX \equiv gcd(mod \ B)$.

所以若使得原同余方程组有解，必须有：$C$ 是$gcd(a,b)$的倍数。

那么我们要找的$t$就等于$X \cdot \frac{C}{gcd}$
那么满足前$k$个同余方程的解就是$ans=ans+t\cdot M$。

接下来更新$M=M\cdot m_k$,而在这里实际上$M$只需要求所有模数的最小公倍数即可，所以可以直接将其乘上$\frac{m_k}{gcd(m_k,M)}$,即$\frac{m_k}{gcd}$即可。

$Code$
```cpp {.line-numbers}
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const ll MAXN = 1e5 + 50;
void read(ll &x){/*Fast input, omit here*/}
ll n,a[MAXN],m[MAXN];
ll ans,M;
ll mult(ll a,ll b,ll p){
	ll ans = 0;
	while(b){
		if(b & 1) ans = (ans + a) % p;
		a = (a + a) % p;
		b >>= 1;
	}
	return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b == 0){
      x = 1; y = 0;
      return a;
    }
	ll gcd = exgcd(b, a%b, y, x);
	y -= (a / b) * x;
	return gcd;
}
ll solve(){
	ans = a[1],M = m[1];
	for(ll i = 2;i <= n;++i){
		ll A = M, B = m[i], C =((a[i] - ans) % B + B) % B, x, y;
		ll gcd = exgcd(A, B, x, y);
        //耐心看………………ovo
		if(C % gcd != 0) return -1;
		x = mult(x, C / gcd, B);
		ans += M * x;
		M *= m[i] / gcd;
		ans = (ans % M + M) % M;
	}
	return ans = (ans % M + M) % M;
}
int main(){
	read(n);
	for(ll i = 1;i <= n;++i){
		read(m[i]), read(a[i]);
	}
	printf("%lld\n", solve());
	return 0;
} 
```