前言

数论总是学了就忘，趁着没忘赶紧写出来

扩展中国剩余定理

为什么是扩展呢，因为不扩展的太菜了，从本质上来说，两者的做法有着本质上的区别，CRT 依靠构造，EXCRT 则是合并（由此可见 EXCRT 适用性更广的原因）。而且时间复杂度一样，码量也区别不大，因此可能还是 EXCRT 更好用一点

证明

（注：本文方法和网上的略有不同）

{x≡c1(mod m1)x≡c2(mod m2)⋮x≡cn(mod mn)\begin{cases} x\equiv c_1(\rm mod\ m_1)\\ x\equiv c_2(\rm mod\ m_2)\\ \vdots\\ x\equiv c_n(\rm mod\ m_n)\\ \end{cases}

因为没了 mm 两两互质的限制，因此只能用合并解决。

首先拿出两个式子：

x≡c1(mod m1)x≡c2(mod m2)\begin{aligned} x\equiv c_1(\rm mod\ m_1)\\ x\equiv c_2(\rm mod\ m_2) \end{aligned}

接着把它们换个形式：

x=k1m1+c1x=k2m2+c2\begin{aligned} x=k_1m_1+c_1\\ x=k_2m_2+c_2 \end{aligned}

联立，接着往下推：

k1m1+c1=k2m2+c2k1m1=c2−c1+k2m2注：这个方程有解的条件是gcd (m1,m2)∣(c2−c1),后文会用到k1m1gcd (m1,m2)=c2−c1gcd (m1,m2)+k2m2gcd (m1,m2)m1gcd (m1,m2)k1=c2−c1gcd (m1,m2)+m2gcd (m1,m2)k2m1gcd (m1,m2)k1≡c2−c1gcd (m1,m2)(mod m2gcd (m1,m2))k1≡c2−c1gcd (m1,m2)m1gcd (m1,m2)−1(mod m2gcd (m1,m2))(mod m2gcd (m1,m2))k1=c2−c1gcd (m1,m2)m1gcd (m1,m2)−1(mod m2gcd (m1,m2))+ym2gcd (m1,m2)x=c2−c1gcd (m1,m2)m1gcd (m1,m2)−1(mod m2gcd (m1,m2))m1+ym1m2gcd (m1,m2)+c1注：这里把k1带入x=k1m1+c1中，就可以求出合并后的式子x≡c2−c1gcd (m1,m2)m1gcd (m1,m2)−1(mod m2gcd (m1,m2))m1+c1(mod m1m2gcd (m1,m2))\begin{aligned} k_1m_1+c_1&=k_2m_2+c_2\\ k_1m_1&=c_2-c_1+k_2m_2\\ \color{green}\text{注：这个方程有解的条件是}&\color{green}\rm gcd\ (m_1,m_2) \mid (c_2-c_1),\text{后文会用到}\\ \dfrac{k_1m_1}{\rm gcd\ (m_1,m_2)}&=\dfrac{c_2-c_1}{\rm gcd\ (m_1,m_2)}+\dfrac{k_2m_2}{\rm gcd\ (m_1,m_2)}\\ \dfrac{m_1}{\rm gcd\ (m_1,m_2)}k_1&=\dfrac{c_2-c_1}{\rm gcd\ (m_1,m_2)}+\dfrac{m_2}{\rm gcd\ (m_1,m_2)}k_2\\ \dfrac{m_1}{\rm gcd\ (m_1,m_2)}k_1&\equiv\dfrac{c_2-c_1}{\rm gcd\ (m_1,m_2)}(\rm mod\ \dfrac{m_2}{\rm gcd\ (m_1,m_2)})\\ k_1&\equiv\dfrac{c_2-c_1}{\rm gcd\ (m_1,m_2)}\dfrac{m_1}{\rm gcd\ (m_1,m_2)}^{-1}(\rm mod\ \dfrac{m_2}{\rm gcd\ (m_1,m_2)})(\rm mod\ \dfrac{m_2}{\rm gcd\ (m_1,m_2)})\\ k_1&=\dfrac{c_2-c_1}{\rm gcd\ (m_1,m_2)}\dfrac{m_1}{\rm gcd\ (m_1,m_2)}^{-1}(\rm mod\ \dfrac{m_2}{\rm gcd\ (m_1,m_2)})+y\dfrac{m_2}{\rm gcd\ (m_1,m_2)}\\ x&=\dfrac{c_2-c_1}{\rm gcd\ (m_1,m_2)}\dfrac{m_1}{\rm gcd\ (m_1,m_2)}^{-1}(\rm mod\ \dfrac{m_2}{\rm gcd\ (m_1,m_2)})m_1+y\dfrac{m_1m_2}{\rm gcd\ (m_1,m_2)}+c_1\\ \color{green}\text{注：这里把}\color{green}k_1\text{带入}x=k_1m_1&\color{green}+c_1\text{中，就可以求出合并后的式子}\\ x&\equiv\dfrac{c_2-c_1}{\rm gcd\ (m_1,m_2)}\dfrac{m_1}{\rm gcd\ (m_1,m_2)}^{-1}(\rm mod\ \dfrac{m_2}{\rm gcd\ (m_1,m_2)})m_1+c_1(\rm mod\ \dfrac{m_1m_2}{\rm gcd\ (m_1,m_2)})\\ \end{aligned}

到这里，我们就可以得到合并后的式子：

令:

{c=c2−c1gcd (m1,m2)m1gcd (m1,m2)−1(mod m2gcd (m1,m2))m1+c1m=m1m2gcd (m1,m2)\\ \begin{cases} c=\dfrac{c_2-c_1}{\rm gcd\ (m_1,m_2)}\dfrac{m_1}{\rm gcd\ (m_1,m_2)}^{-1}(\rm mod\ \dfrac{m_2}{\rm gcd\ (m_1,m_2)})m_1+c_1\\ m=\dfrac{m_1m_2}{\rm gcd\ (m_1,m_2)} \end{cases}

则有:

x≡c(mod m)x\equiv c(\rm mod\ m)

照着写就行了……
（一定要给 c,mc, m 赋为最先输入的 不然过不了n=1）

code:

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
//problem: 
//date: 2023.11.10-14:35
#include <bits/stdc++.h>
#define int __int128 
#define FH signed
using namespace std;

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

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

int inv(int a, int b)
{
    int x, y;
    exgcd(a, b, x, y);
    while (x < 0) x += b;
    return x;
}

int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

FH main()
{
    int n;
    n = read();

    int c1, c2, m1, m2, c, m;
    m1 = read(), c1 = read();
    c = c1, m = m1;//!!!!!!!!!!
    for(int i = 2; i <= n; i ++)
    {
        m2 = read(), c2 = read();
        int d = gcd(m1, m2);
        if((c2 - c1) % d != 0)
        {
            cout << -1;
            return 0;
        }
        m = (m1 * m2) / d;
        c = (inv(m1 / d, m2 / d) * (c2 - c1) / d) % (m2 / d) * m1 + c1;
        c = (c % m + m) % m;
        c1 = c, m1 = m;
    }
    cout << (long long)c << "\n";
    return 0;
}