扩展中国剩余定理

实际上是同余方程组的合并

简述

如果给定$n$个同余方程组
$$
\begin{cases}
x &\equiv b_1 \pmod {a_1} \\
x &\equiv b_2 \pmod {a_2} \\
x &\equiv b_3 \pmod {a_3} \\
&\cdots \\
x &\equiv b_n \pmod {a_n} \\
\end{cases}
$$
保证$a$是正整数，$b$是非负整数

现在要求找一个非负整数$x$，使得$x$最小且满足这$n$同余方程

数据保证$x$不超过$10^{18}$

题解

现在考虑合并两个同余方程的时候该怎么做
$$
\begin{cases}
x \equiv b \pmod {a} \\
x \equiv B \pmod {A}
\end{cases}
$$
这个可以写作
$$
\begin{cases}
x = ay + b \\
x = AY + B
\end{cases}
$$
由于$x$是一个常量，因此$ay+b=AY+B$，其中$a,b,A,B$都是常数

整理一下后就是$ay+A(-Y)=B-b$

通过$exgcd$，可以获得一组关于$ay+A(-Y)=\gcd(a,A)$的解$(y_0,-Y_0)$

即$a(y_0 \times \frac{B-b}{\gcd(a,A)})+A(-Y_0 \times \frac{B-b}{\gcd(a,A)})=\gcd(a,A) \times \frac{B-b}{\gcd(a,A)}=B-b$

由于$x=ay+b$，现在要最小化$x$，也就是最小化$y$，即最小化$t=y_0 \times \frac{B-b}{\gcd(a,A)}$

由于$t$的通解为$t+\frac{A}{\gcd(a,A)}k$，因此$t$的最小值为$t_0=t \bmod \frac{A}{\gcd(a,A)}$

于是就可以将这两个同余方程合并为
$$
x \equiv a \times t_0+b \pmod {\mathbb{lcm}(a,A)}
$$

代码

#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int N = 1e5 + 10;
ll x, y, d; int n;

void exgcd(ll &x, ll &y, ll a, ll b) {
    if(!b) d = a, x = 1, y = 0;
    else exgcd(y, x, b, a % b), y -= a / b * x;
}

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

ll a, b, A, B;

void merge() {
    exgcd(x, y, a, A);
    ll c = B - b;
    if(c % d) puts("-1"), exit(0);
    x = x * c / d % (A / d);
    if(x < 0) x += A / d;
    ll mod = lcm(a, A);
    b = (a * x + b) % mod; if(b < 0) b += mod;
    a = mod;
}

int main() {
    scanf("%d", &n);
    for(int i = 1 ; i <= n ; ++ i) {
        long long _A, _B;
        scanf("%lld%lld", &_A, &_B), A = _A, B = _B;
        if(i > 1) merge();
        else a = A, b = B;
    }
    printf("%lld\n", (long long)(b % a));
}