题解 P4777 【【模板】扩展中国剩余定理（EXCRT）】
sumijie
2018-09-22 20:47:19
## 对于一组同余方程
$\begin{cases} x \equiv a_1\ ({\rm mod}\ n_1) \\ x\equiv a_2\ ({\rm mod}\ n_2) \\ ... \\ x \equiv a_n\ ({\rm mod}\ n_n)\end{cases} $
**对于第一个和第二个式子**
**则有：**
$x = a_1 + k_1*n_1$
$x = a_2 + k_2*n_2$
**就有：**
$a_1 + k_1*n_1 = a_2 + k_2*n_2$
$k_1*n_1 - k_2*n_2 = a_2 - a_1$
**故我们设 $d = a_2 - a_1$**
**再变化一下形式就有：**
$k_1*n_1 + (-k_2)*n_2 = d$
**令 $g = gcd(n_1,n_2)$**
**这样我们就可以通过exgcd来求出一组解 $x_1,y_1$**
**满足 $x_1*n_1 + y_2*n_2 = g$**
**故：**
$x_1*d/g *n_1 + y_2*d/g*n_2 = g*d/g$
**则：**
$k_1 = x_1*d/g,k_2 = y_1*d/g$
**从而得到一组通解**
$k_1 = k_1 + n2/g*T$
$k_2 = k_2 - n1/g*T$
**要使所求得的解最小且为正整数则可以根据 $k_1$ 的通解形式求得**
$ k_1 = (k_1\%(n_2/g) + n_2/g)\%(n_2/g) $
**再带入 $x = a_1 + k_1*n_1$ 得到 $x$ **
**令 $A$ 为合并后的 $a$ , $N$ 为合并后的 $n$**
**所以$N = lcm(n_1,n_2) = n_1 * n_2 / g$**
**根据$x \equiv A\ ({\rm mod}\ N)$ 且 $x$ 是满足该式子最小的值**
**得到：**
$A = x$
# 欢迎来卡
```cpp
#include<iostream>
typedef __int128 ll;
using namespace std;
void exgcd(ll a,ll b,ll &g,ll &x,ll &y) {
if (b == 0) {
g = a;
x = 1;
y = 0;
return;
}
exgcd(b,a%b,g,y,x);
y-=(a/b)*x;
}
bool flag = false;
ll a1,a2,n1,n2;
ll abs(ll x) {
return x>0?x:-x;
}
void china() {
ll d = a2 - a1;
ll g,x,y;
exgcd(n1,n2,g,x,y);
if (d % g == 0) {
x = ((x*d/g)%(n2/g)+(n2/g))%(n2/g);
a1 = x*n1 + a1;
n1 = (n1*n2)/g;
}
else
flag = true;
}
int n;
long long as[100001];
long long ns[100001];
ll realchina() {
a1 = as[0];
n1 = ns[0];
for (ll i = 1;i<n;i++) {
a2 = as[i];
n2 = ns[i];
china();
if (flag)
return -1;
}
return a1;
}
int main() {
cin>>n;
flag = false;
for (ll i = 0;i<n;i++)
cin>>ns[i]>>as[i];
cout<<(long long)realchina()<<endl;
}
```