扩展中国剩余定理

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

给定 \(n\) 组非负整数 \(a_i, b_i\) ，求解关于 \(x\) 的方程组的最小非负整数解。

\[\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}\]

对于 \(100 \%\) 的数据，\(1 \le n \le {10}^5\)， \(1 \le b_i,a_i \le {10}^{12}\)，保证所有 \(a_i\) 的最小公倍数不超过 \({10}^{18}\)。

请注意程序运行过程中进行乘法运算时结果可能有溢出的风险。

数据保证有解。

与中国剩余定理（CRT）不同的是，本题的模数不保证互质

那么之前的算法就彻底崩了，因为逆元不一定存在

换一个思路，我们能不能两两合并同余方程呢？

即已知同余方程组

\[\begin{cases} x \equiv b \pmod{a} \\ x \equiv B \pmod{A} \end{cases}\]

找到一组 \((a',b')\) 使得 \(x \equiv b' \pmod{a'}\) 与上面方程组等价

我们设 \(y \in \mathbf{Z}\) 是一个特解，那么沿用P1082 [NOIP 2012 提高组] 同余方程的思路，就可以转化为： \(\exist t,T \in \mathbf{Z}\)，使得

\[\begin{cases} y = at + b \\ y = AT + B \end{cases}\]

整理得到

\[AT - at = b - B\]

容易发现这是一个不定方程，我们使用exgcd求出一组 \((T,t)\)，使得 \(AT - at = g\)，其中 \(g = \gcd(A, -a)\)

如果 \(b-B\) 不是 \(g\) 的倍数，那么原方程组无解

否则给 \(t,T\) 都乘上 \(d = \frac{b-B}{g}\) 即可

那么就有 \(y = at + b\)，因此就有 \(a' = \text{lcm}(A,a), b' = y \ \text{mod} \ a'\)

两两合并所有同余方程即可

实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef __int128 ll;
namespace IO
{
    inline ll read()
    {
        ll x = 0, f = 1;
        char ch = getchar();
        while (ch > '9' || ch < '0')
        {
            if (ch == '-')
                f = -1;
            ch = getchar();
        }
        while (ch <= '9' && ch >= '0')
            x = (x << 3) + (x << 1) + (ch - '0'), ch = getchar();
        return x * f;
    }
    void write(ll x)
    {
        if (x < 0)
            putchar('-'), x = -x;
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
    inline void writeln(ll x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace IO;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x * y / gcd(x, y); }
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
ll a, b, A, B, n;
void merge(ll &a, ll &b, ll A, ll B)
{
    ll t, T, g;
    g = exgcd(A, -a, T, t);
    if((b - B) % g)
    {
        writeln(-1);
        exit(0);
    }
    t *= (b - B) / g;
    ll l = lcm(a, A);
    b = ((a * t + b) % l + l) % l;
    a = l;
}
int main()
{
    n = read();
    n--;
    a = read(), b = read();
    while(n--)
    {
        A = read(), B = read();
        merge(a, b, A, B);
    }
    writeln(b);
    return 0;
}