# 中国剩余定理 与 扩展中国剩余定理 

### 一、问题引入
先看一道$poj$上的题目：[【$POJ1006$】 $Biorhythms$](http://poj.org/problem?id=1006)

**题意**：
　　人自出生起就有体力，情感和智力三个生理周期，分别为$23$，$28$和$33$天。一个周期内有一天为峰值，在这一天，人在对应的方面（体力，情感或智力）表现最好。通常这三个周期的峰值不会是同一天。现在给出三个日期，分别对应于体力，情感，智力出现峰值的日期。然后再给出一个 **起始日期**$d$，要求从这一天开始，算出最少再过多少天后三个峰值同时出现。

**分析**：
　　首先我们知道，**任意两个峰值之间一定相距整数倍的周期**。假设一年的第$N$天达到峰值，则 **下次** 达到峰值的时间为$N+kT$($T$是周期，$k$是任意正整数)。

所以，三个峰值同时出现的那一天($S$)应满足

$$
\large \left\{\begin{matrix}
S=N_1+T_1∗k_1 & ① \\ 
S=N_2+T_2∗k_2 & ② \\ 
S=N_3+T_3∗k_3 & ③ \\ 
\end{matrix}\right.
$$

$N_1,N_2,N_3$分别为为体力，情感，智力出现峰值的日期， $T_1,T_2,T_3$ 分别为体力，情感，智力周期。 需要求出$k_1,k_2,k_3$三个非负整数使上面的等式成立。

想直接求出$k_1,k_2,k_3$很难，但是目的是求出$S$， 可以考虑 **从结果逆推**。根据上面的等式，$S$ 满足三个要求：
- 除以$T_1$余数为$N_1$
- 除以$T_2$余数为$N_2$
- 除以$T_3$余数为$N_3$

**找到最小的一个这样的数就可以了。**

这就是著名的 **中国剩余定理**，老祖宗在几千年前已经对这个问题想出了一个精妙的解法。依据此解法的算法，时间复杂度可达到$O(1)$。

###  二、中国剩余定理
在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以$3$余$2$），五五数之剩三（除以$5$余$3$），七七数之剩二（除以$7$余$2$），问物几何？”这个问题称为 **孙子问题** ，该问题的一般解法国际上称为 **中国剩余定理**。

**解法共三步**

- ① 找三个数：
  - 从$3$和$5$的公倍数中找出被$7$除余$1$的最小数$15$
  - 从$3$和$7$的公倍数中找出被$5$除余$1$的最小数$21$
  - 从$5$和$7$的公倍数中找出被$3$除余$1$的最小数$70$
  
  
- ② 找符合条件的一个数：
  - 用$15$乘以$2$（$2$为最终结果除以$7$的余数）
  - 用$21$乘以$3$（$3$为最终结果除以$5$的余数）
  - 用$70$乘以$2$（$2$为最终结果除以$3$的余数）
  然后把三个乘积相加$15∗2+21∗3+70∗2=233$

- ③ 用$233$除以$3，5，7$三个数的最小公倍数$105$，得到余数，即$233\%105=23$

<font color='red' size=4><b>答：$23$就是符合条件的最小数</b></font>

**$Q$:这有数学依据吗？**
 现在将 **孙子问题** 拆分成几个简单的小问题，从零开始，揣测古人是如何推导出这个解法的：

首先，我们假设:
- $n_1$是满足除以$3$余$2$的一个数，比如$2，5，8$等等，也就是满足$3∗k_1+2（k_1>=0）$ 的一个任意数。
- $n_2$是满足除以$5$余$3$的一个数，比如$3，8，13$等等，也就是满足$5∗k_2+3（k_2>=0）$ 的一个任意数。
- $n_3$是满足除以$7$余$2$的一个数，比如$2，9，16$等等，也就是满足$7∗k_3+2（k_3>=0）$ 的一个任意数。

有了前面的假设，我们先从$n_1$这个角度出发，已知$n_1$满足除以$3$余$2$，能不能使得$n_1+n_2$的和仍然满足除以$3$余$2$,进而使得$n_1+n_2+n_3$的和仍然满足除以$3$余$2$？

　这就牵涉到一个 **最基本数学定理**，如果有$a\%b=c$，则有$(a+k∗b)\%b=c$($k$为非零整数)，换句话说，如果一个除法运算的余数为$c$，那么被除数与$k$倍的除数相加（或相减）的和（差）再与除数相除，余数不变。

以此定理为依据，如果$n_2$是$3$的倍数，$n_1+n_2$就依然满足除以$3$余$2$。同理，如果$n_3$也是$3$的倍数，那么$n_1+n_2+n_3$的和就满足除以$3$余$2$。这是从$n_1$的角度考虑的，再从$n_2$，$n_3$的角度出发，我们可推导出以下三点：

- 为使$n_1+n_2+n_3$的和满足除以$3$余$2$，$n_2$和$n_3$必须是$3$的倍数

- 为使$n_1+n_2+n_3$的和满足除以$5$余$3$，$n_1$和$n_3$必须是$5$的倍数

- 为使$n_1+n_2+n_3$的和满足除以$7$余$2$，$n_1$和$n_2$必须是$7$的倍数

因此，为使$n_1+n_2+n_3$的和作为 **孙子问题** 的一个最终解，需满足：

* $n_1$除以$3$余$2$，且是$5$和$7$的公倍数
* $n_2$除以$5$余$3$，且是$3$和$7$的公倍数
* $n_3$除以$7$余$2$，且是$3$和$5$的公倍数

所以，孙子问题解法的 **本质** 是:
- 从$5$和$7$的公倍数中找一个除以$3$余$2$的数$n_1$
- 从$3$和$7$的公倍数中找一个除以$5$余$3$的数$n_2$
- 从$3$和$5$的公倍数中找一个除以$7$余$2$的数$n_3$

再将三个数相加得到解。在求$n_1，n_2，n_3$时又用了一个 **小技巧**，以$n_1$为例，并非从$5$和$7$的公倍数中直接找一个除以$3$余$2$的数，而是
<font color='red' size=4><b>
 先找一个 除以$3$余$1$的数，再乘以$2$。也就是先求出$5$和$7$的公倍数模$3$下的逆元 ，再用逆元去乘余数!</b></font>

> **$Q$:为啥这样干呢？**
**答**：不这样干不好整啊，$5$和$7$的公倍数可不少，一个个暴力去找太累了。不这样暴力还能咋办？
`(a / b) % p = (a%p / b%p) %p （错）`
因为除法没法进行取模运算，需要找到乘法逆元。
**$Q$:哪里来的除法，哪里来的取模？**
**答**:$M_i=M/m_i$就是除法，需要对$m_i$取模。



这里**又有一个数学公式**，如果$a\%b=c$，那么$(a∗k)\%b=a\%b+a\%b+…+a\%b=c+c+…+c=k∗c(k>0)$,也就是说，如果一个除法的余数为$c$，那么被除数的$k$倍与除数相除的余数为$k∗c$,展开式中已证明。

最后，我们还要清楚一点，$n_1+n_2+n_3$只是问题的一个解，并不是最小的解。如何得到最小解？我们只需要从中最大限度的减掉$3，5，7$的公倍数$105$即可。道理就是前面讲过的定理 **如果$a\%b=c$，则有$(a−k∗b)\%b=c$** ,所以$(n_1+n_2+n_3)\%105$就是最终的最小解。


#### 【中国剩余定理】
设$x \in Z$,有

$$
\large \left\{\begin{matrix}
 x \equiv m_1(mod \ a_1) & \\ 
 x \equiv m_2(mod \ a_2) & \\
 x \equiv m_3(mod \ a_3) & \\
 ... &  \\
 x \equiv m_n(mod \ a_n) &
\end{matrix}\right.
$$

令$ \large \left\{\begin{matrix}
A=a_1*a_2*a_3...*a_n & \\ 
A_i=A/a_i& \\
t_i 是A_i关于a_i 的逆元，即A_i*t_i \equiv 1 (mod \ a_i)
\end{matrix}\right.$

则
$$\large res=\sum_{i=1}^{n}m_iA_it_i$$

#### 【扩展欧几里得求逆元】
扩展欧几里得算法，顾名思义，是欧几里得算法的扩展，这意味着该算法不仅保留了欧几里得算法的核心——求最大公约数，还具备欧几里得算法没有的功能——**求解贝祖等式**,即可以求出方程$ax+by=c$的一组解$(x_0,y_0)$

特别的，当 $gcd(a,b)=1$ ,即$a,b$互素时，$ax+by=1$中的解 
- $x$ 是$a$模$b$的乘法逆元，即$a * x \equiv 1(mod \ b)$
- $y$ 是$b$模$a$的乘法逆元，即$b * x \equiv 1(mod \ a)$

> **解释**:方程$ax+by=1$写成同余方程，就是:$a * x \equiv 1(mod \ b)$,也就是逆元的定义式
#### 【`r = (r % a + a) % a`】
**作用**：将余数加上若干个循环节，使得结果落在$0 \sim a-1$之间。 

 **举栗子**：
按$5$个一组划分，最后缺少$2$个

本质：就是多了$3$个,$r$其实是$3$

$Q$:那就直接$r+a=3$不就行了吗，$(r\%a+a)\%a$是什么意思？

$A:(1)$如果$r>=0, r+a>=a$了，这时应该再多分出去一组才对，不能直接$r+a$ ,但 $(r\%a+a)\%a$就没有问题了
$ (2)$如果$r<0,(r\%a+a)\%a$也一样正确

**结论**：公式 $(r\%a+a)\%a$可以把负的余数改为正的余数

```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
int main() {
 
    int r = -2, a = 5;
    r = (r % a + a) % a;
    cout << r << endl;
    // 输出3
    return 0;
}
```

### 三、扩展中国剩余定理

**$Q$:中国剩余定理要求所有的$m_i$互质,那么如果不互质，怎么求解同余方程组?**
答：对于模数不互质的情况，我们可以通过合并相邻两组方程的方式来逐步得到解。

$$
\large \left\{\begin{matrix}
 x \equiv m_1 \ (mod \ a_1) & ① \\ 
 x \equiv m_2 \ (mod \ a_2) & ② \\ 
 ... \\
 x \equiv m_n \ (mod \ a_n) &  \\ 
\end{matrix}\right.
$$

先计算两个线性同余方程组的解，之后依此类推
① 可以写成$x=k_1*a_1+m_1$ ③
② 可以写成$x=k_2*a_2+m_2$ ④

③=④ $ \rightarrow $ $k_1*a_1+m_1=k_2*a_2+m_2$ $ \rightarrow$ $k_1*a_1-k_2*a_2=m_2-m_1$ ⑤

根据 **裴蜀定理**,当
$m_2-m_1$为 $gcd(a_1,-a_2)$的倍数时，方程 ⑤ 有无穷多组整数解

而$k_1*a_1-k_2*a_2=gcd(a_1,-a_2)=d$，可以用 **拓展欧几里得算法** 来求解出一组**特解($k_1',k_2'$)**，即$exgcd(a_1,-a_2,k_1',k_2')$

**如何求解$k_1*a_1-k_2*a_2=gcd(a_1,-a_2)=d$中的通解$k_1,k_2$呢？**

**结论:$k_1,k_2$的通解**
$$
\large \left\{\begin{matrix}
 k_1=k_1'+k*\frac{a_2}{d} \\ 
 k_2=k_2'+k*\frac{a_1}{d} 
\end{matrix}\right.
$$

**证明**:
$k_1$的通解为$s_1$,$k_2$的通解为$s_2$,$k_1$的特解为$k_1'$,$k_2$的特解为$k_2'$

则 
$$
\large \left\{\begin{matrix}
a_1*s_1-a_2*s_2=d & \\ 
a_1*k_1'-a_2*k_2'=d & 
\end{matrix}\right.
$$

$$↓方程组同时除d$$


$$
\large \left\{\begin{matrix}
\frac{a_1}{d}*s_1-\frac{a_2}{d}*s_2=1 &  \\ 
\frac{a_1}{d}*k_1'-\frac{a_2}{d}*k_2'=1 & 
\end{matrix}\right.
$$

$$↓相减下$$

$$\frac{a_1}{d}*(s_1-k_1')-\frac{a_2}{d}*(s_2-k_2')=0$$

$\because$ $gcd(a_1,-a_2)=d$，$\therefore \frac{a_1}{d}$与$\frac{a_2}{d}$互质。
>**解释**：最大公约数嘛，如果除完了还有约数，那还是什么最大公约数~

$\therefore \frac{a_2}{d} \mid s_1-k_1', \frac{a_1}{d} \mid s_2-k_2'$

$\therefore s_1-k_1'=k*\frac{a_2}{d} \rightarrow k_1=k_1'+k*\frac{a_2}{d}$整除式变形

$\therefore s_2-k_2'=k*\frac{a_1}{d} \rightarrow k_2=k_2'+k*\frac{a_1}{d}$整除式变形

将$k_1$通解代入 ③ 得

$$ x=k_1*a_1+m_1=(k_1'+k*\frac{a_2}{d})*a_1+m_1= \underbrace{k_1'*a_1+m_1}_{更新后的m_1}+ \overbrace{\frac{a_2}{d}*a_1}^{更新后的a_1}*k$$

对照原方程$x=a_1*k_1+m_1,x=a_2*k_2+m_2$,我们发现，两个方程合并后得到的新方程，其实和原来的两个方程都是差不多的样子，只不过系数发生了变化,而合并后的方程肯定是即符合 ① 双符合 ②, 如果继续迭代下去，迭代$n-1$次后，可以将$n$个线性同余方程合并为一个方程,最终方程就能满足所有的约束要求。为了能够实现代码循环迭代，那么就可以

$$
\large \left\{\begin{matrix}
m_1=k_1'*a_1+m_1 & \\ 
a_1=\frac{a_2}{d}*a_1*k & 
\end{matrix}\right.
$$
这样反复循环迭代就可以找出最后一全兼容方程了！

**$Q$:此处为什么要取绝对值呢**
$A$：因为不知道$\frac{a_2}{d}$的正负性，我们在原基础上要尽量减多个$abs(\frac{a_2}{d})$，使其为正整数且最小。



### 四、练习题

#### 模数互质

**[$P1495$ 【模板】中国剩余定理($CRT$)/曹冲养猪](https://www.luogu.com.cn/problem/P1495)**

$Code$ **中国剩余定理解法**

```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define endl "\n"
const int N = 20;
typedef __int128 INT128;

int n;     // 同余方程个数
int a[N];  // 除数数组
int m[N];  // 余数数组
int A = 1; // 除数累乘积
int x, y;  // (x,y)是方程 Mi * x + m[i] * y = 1的一个解，x是Mi关于m[i]的逆元
int res;   // 最小整数解
// 扩展欧几里得模板
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;
}

// 中国剩余定理模板
void CRT() {
    //  一、预处理
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> m[i];                // 读入除数数组和余数数组
        m[i] = (m[i] % a[i] + a[i]) % a[i]; // ① 预算余数为正数： r[i]可能为负数，预处理成正数,本题没有这个要求，但考虑到通用模板，加上了这块代码
        A *= a[i];                          // ② 预处理除数连乘积
    }
    // 二、计算
    // 功能: 求 x ≡ r_i mod m_i 方程组的解
    for (int i = 1; i <= n; i++) {
        int Ai = A / a[i];                                 // ①除数连乘积除去当前的除数，得到Mi
        exgcd(Ai, a[i], x, y);                             // ②扩欧求逆元
        x = (x % a[i] + a[i]) % a[i];                      // ③逆元防负数
        res = (res + INT128(m[i] * A / a[i] * x) % A) % A; // ④累加res（看公式） 快速乘,防止LL也在乘法过程中爆炸
    }
}

signed main() {
    cin >> n;
    CRT();
    cout << res << endl;
}
```

$Code$ **扩展中国剩余定理解法**
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

const int N = 100010;
int a[N], m[N];
int n;
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 exCRT() { // m代表合并多少次，有n个方程，其实m=n-1
    int a1 = a[1], m1 = m[1], a2, m2, k1, k2;

    for (int i = 2; i <= n; i++) { // a1,m1：做为先遣军，准备与后续的方程合并
        a2 = a[i], m2 = m[i];
        int d = exgcd(a1, -a2, k1, k2); // 扩展欧几里得求方程特解,x有用，y无用
        if ((m2 - m1) % d) return -1;   // 拼出来的同余方程无解，继续不下去
        k1 *= (m2 - m1) / d;            // 同比扩大指定倍数
        int t = abs(a2 / d);            // 最小累计单元
        k1 = (k1 % t + t) % t;          // 取得最小正整数解，否则可以会在计算过程中爆long long
        m1 = k1 * a1 + m1;              // 准备下一轮的m[1],a[1]
        a1 = abs(a1 / d * a2);          // 两个顺序不能反
    }
    return (m1 % a1 + a1) % a1; // 取得最小正整数解
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> m[i];
    cout << exCRT() << endl;
}
```

[【$POJ1006$】 $Biorhythms$](http://poj.org/problem?id=1006)

$Code$ **中国剩余定理解法**
```cpp {.line-numbers}
#include <cstdio>
#include <iostream>
using namespace std;
#define endl "\r"
#define int long long

const int N = 10;

int n = 3;
int a[N] = {0, 23, 28, 33};
int m[N];
int A = 1;
int x, y;
int res;

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 qmul(int a, int b, int mod) {
    int res = 0;
    while (b) {
        if (b & 1) res = (res + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}

void CRT() {
    for (int i = 1; i <= n; i++) {
        m[i] = (m[i] % a[i] + a[i]) % a[i];
        A *= a[i];
    }

    for (int i = 1; i <= n; i++) {
        int Ai = A / a[i];
        exgcd(Ai, a[i], x, y);
        x = (x % a[i] + a[i]) % a[i];
        res = (res + qmul(m[i], A / a[i] * x, A)) % A;
    }
}

int T;
int p, e, i, d;
signed main() {
    while (cin >> p >> e >> i >> d && ~p) {
        T++;
        A = 1;
        res = 0;
        m[1] = p, m[2] = e, m[3] = i;
        CRT();
        if (res <= d) res += A;
        printf("Case %lld: the next triple peak occurs in %lld days.\n", T, res - d);
    }
}
```
**$Code$ 扩展中国剩余定理**

```cpp {.line-numbers}
#include <cstdio>
#include <iostream>
#include <stdlib.h>
using namespace std;
#define int long long
#define endl "\r"
const int N = 10;

int n = 3;
int a[N] = {0, 23, 28, 33};
int m[N];
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 exCRT() { // m代表合并多少次，有n个方程，其实m=n-1
    int a1 = a[1], m1 = m[1], a2, m2, k1, k2;

    for (int i = 2; i <= n; i++) { // a1,m1：做为先遣军，准备与后续的方程合并
        a2 = a[i], m2 = m[i];
        int d = exgcd(a1, -a2, k1, k2); // 扩展欧几里得求方程特解,x有用，y无用
        if ((m2 - m1) % d) return -1;   // 拼出来的同余方程无解，继续不下去
        k1 *= (m2 - m1) / d;            // 同比扩大指定倍数
        int t = abs(a2 / d);            // 最小累计单元
        k1 = (k1 % t + t) % t;          // 取得最小正整数解，否则可以会在计算过程中爆long long
        m1 = k1 * a1 + m1;              // 准备下一轮的m[1],a[1]
        a1 = abs(a1 / d * a2);          // 两个顺序不能反
    }
    return (m1 % a1 + a1) % a1; // 取得最小正整数解
}

int T;
int m1, m2, m3, d;
signed main() {
    while (cin >> m[1] >> m[2] >> m[3] >> d && ~m[1]) {
        T++;
        int res = exCRT();
        int A = a[1] * a[2] * a[3];
        if (res <= d) res += A;
        printf("Case %lld: the next triple peak occurs in %lld days.\n", T, res - d);
    }
}
```

[$P3868$ [$TJOI2009$] 猜数字](https://www.luogu.com.cn/problem/P3868)

**$Code$ 中国剩余定理实现代码**
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N = 20;

int qmul(int a, int b, int mod) {
    int res = 0;
    while (b) {
        if (b & 1) res = (res + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}

int n;
int a[N];
int m[N];
int A = 1;
int x, y;
int res;

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;
}

void CRT() {
    for (int i = 1; i <= n; i++) cin >> m[i];
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) {
        m[i] = (m[i] % a[i] + a[i]) % a[i];
        A *= a[i];
    }

    for (int i = 1; i <= n; i++) {
        int Mi = A / a[i];
        exgcd(Mi, a[i], x, y);
        x = (x % a[i] + a[i]) % a[i];
        res = (res + qmul(m[i], A / a[i] * x, A)) % A;
    }
}

signed main() {
    cin >> n;
    CRT();
    cout << res << endl;
}
```

**$Code$ 扩展中国剩余定理实现代码**
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N = 100010;
int a[N], m[N];
int n;
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 exCRT() { // m代表合并多少次，有n个方程，其实m=n-1
    int a1 = a[1], m1 = m[1], a2, m2, k1, k2;

    for (int i = 2; i <= n; i++) { // a1,m1：做为先遣军，准备与后续的方程合并
        a2 = a[i], m2 = m[i];
        int d = exgcd(a1, -a2, k1, k2); // 扩展欧几里得求方程特解,x有用，y无用
        if ((m2 - m1) % d) return -1;   // 拼出来的同余方程无解，继续不下去
        k1 *= (m2 - m1) / d;            // 同比扩大指定倍数
        int t = abs(a2 / d);            // 最小累计单元
        k1 = (k1 % t + t) % t;          // 取得最小正整数解，否则可以会在计算过程中爆long long
        m1 = k1 * a1 + m1;              // 准备下一轮的m[1],a[1]
        a1 = abs(a1 / d * a2);          // 两个顺序不能反
    }
    return (m1 % a1 + a1) % a1; // 取得最小正整数解
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> m[i];
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << exCRT() << endl;
}
```

#### 模数不互质

**[洛谷$P4777$ 【模板】扩展中国剩余定理（$EXCRT$）](https://www.luogu.com.cn/problem/P4777)**.

**[$AcWing$ $204$. 表达整数的奇怪方式](https://www.acwing.com/problem/content/206/)**

上面两道题是同一道题，代码是一样的。

```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

const int N = 100010;
int a[N], m[N];
int n;
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 exCRT() { // m代表合并多少次，有n个方程，其实m=n-1
    int a1 = a[1], m1 = m[1], a2, m2, k1, k2;

    for (int i = 2; i <= n; i++) { // a1,m1：做为先遣军，准备与后续的方程合并
        a2 = a[i], m2 = m[i];
        int d = exgcd(a1, -a2, k1, k2); // 扩展欧几里得求方程特解,x有用，y无用
        if ((m2 - m1) % d) return -1;   // 拼出来的同余方程无解，继续不下去
        k1 *= (m2 - m1) / d;            // 同比扩大指定倍数
        int t = abs(a2 / d);            // 最小累计单元
        k1 = (k1 % t + t) % t;          // 取得最小正整数解，否则可以会在计算过程中爆long long
        m1 = k1 * a1 + m1;              // 准备下一轮的m[1],a[1]
        a1 = abs(a1 / d * a2);          // 两个顺序不能反
    }
    return (m1 % a1 + a1) % a1; // 取得最小正整数解
}
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> m[i];
    cout << exCRT() << endl;
}
```