阅读本文所需前置知识：欧几里得算法及其扩展，乘法逆元

# 中国剩余定理

中国古代的数学巨著《孙子算经》中提到一个 “物不知数” 问题，原文如下：” 有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？“。

用现代语言解释，既，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

现代数论中，中国剩余定理，是一个关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的准则以及求解方法。

# 前置知识：一元线性同余方程

在数论中，线性同余方程是最基本的同余方程，“线性” 表示方程只有一个未知数，即形如：${ax\equiv b {\pmod {m}}}$ 的方程。

# 如何求出未知数 x 呢？

1. 根据同余的含义：$(ax-b) \bmod m = 0$ ，那么一定有整数 y 使得 $my+b = ax$ 。
2. 把 my 移动到右面，得到：$ax-my=b$ 。
3. 如果我们假设 $y^\prime=-y$ ，那么步骤二的方程可以写为：$ax+my^\prime=b$ 。
4. 根据裴蜀定理，上面的方程有解的前提是 gcd(a,m)|b ，其中 | 表示整除。
5. 用扩展欧几里德算法求出一组整数 $x_0, y_0$ ，使得$ax_0 + my_0=gcd(a, m)$ 。
6. 现在有两组等式：1. $ax+my^\prime=b$ ；2. $ax_0 + my_0=gcd(a, m)$ 。其中 b 又一定是 gcd(a,m) 的倍数，那么我们只要将 等式2 两面同时扩大 b/gcd(a,m) 倍不就能得到 等式1 了嘛。
7. 扩大后就得到了$x=x_0*b/gcd(a,m)$ 。
8. 此时$b/gcd(a,m)$ 的系数是 1，那么我们只要把这个系数扩展到全部整数，就得到了 x 的通解：${x_{0}+k{\frac {n}{d}}\mid k\in \mathbb {Z}}$ ，其中 d=gcd(a,m) 。

# Code

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组数据 a,b,m。

输入样例
2
2 3 6
4 3 5

输出样例
impossible
-3

#include <iostream>

using namespace std;

typedef long long LL;

int exgcd(int a, int m, int &x, int &y) {

    if (!m) {

        x = 1, y = 0;

        return a;

    }

    int d = exgcd(m, a % m, y, x);

    y -= a / m * x;

    return d;

}

int main() {

    int n;

    cin >> n;

    while (n -- ) {

        int a, b, m, x, y;

        cin >> a >> b >> m;

        int d = exgcd(a, m, x, y);

        if (b % d) puts("impossible");

        // 最后结果对 m 取模是为了让答案保持在 m 之内。

        else cout << (LL)x * b / d % m << endl;

    }

    return 0;

}

# 标准中国剩余定理的推导

在上面，我们知道了单个线性同余方程的求解方法，那么如果线性同余方程扩展为线性同余方程组呢？

对于问题$\forall i\in [1,n],x\equiv a_i (\bmod m_i)$ ，若其中$m_1, m_2,...,m_n$ 满足两两互质，则可以使用标准的中国剩余定理求解，形如：

$$\left\{\begin{matrix} x\equiv a_1 (\bmod m_1) \\ x\equiv a_2 (\bmod m_2)\\ \vdots \\ x\equiv a_n (\bmod m_n)\\ \end{matrix}\right.$$

求解公式 $x=\sum_{i=1}^{n} a_iM_it_i$

其中$M=m_1*m_2*m_3*...*m_n$ ，$M_i=M/m_i$ (也就是除了$m_i$ 以外的$n-1$ 个数的乘积) ，$t_i$ 为$M_i$ 的逆元。即，$t_iM_i \equiv 1 (\bmod m_i)$。

# 公式证明

在上面公式的基础上左右两面同时乘以 $a_i$ ，得到： $a_it_iM_i \equiv a_i {(\bmod m_i)}$ 。

又因为当$j\ne i$ 时，每个$M_j$ 中都被乘了一个$m_i$ （没明白的，再看一遍$M_j$ 的定义），所以有 $a_jt_jM_j \equiv 0 {(\bmod m_i)}$。

所以当 i=1 时，对于求解公式$x=a_1M_1t_1+a_2M_2t_2+a_3M_3t_3+...+a_kM_kt_k$ 中的每一项除了$a_1M_1t_1=a_1 * 1=a_1$ 之外，全部是$a_kM_kt_k=a_k*0$ 。所以有$x=a_1*1 + a_2 * 0 + ... + a_k * 0 =a_1 （\bmod m_1）$ ，那么当 i 取其他值时候同理。这样我们就证明了最终的线性同余方程组的求解公式，也就是中国剩余定理。

# 举个例子

（公式推导实在太抽象了。不如使用实际的例子推一遍来的清晰。）
以《孙子算经》里面的 “物不知数” 问题为例，其中的线性同余方程组是:

$\left\{\begin{matrix} x\equiv 2 (\bmod 3) \\ x\equiv 3 (\bmod 5)\\ x\equiv 2 (\bmod 7)\\ \end{matrix}\right.$

1. 首先把例子给的值对应到模型上，其中$a_1=2,a_2=3,a_3=2$，$m_1=3,m_2=5,m_3=7$ 。
2. 首先算出 M，$M=3*5*7=105$ ，再依次求出$M_1,M_2,M_3$ ，$M_1=M/m_1=35,M_2=21,M_3=15$ ， 算出$M_i$ 的逆元$t_i$ ，其中因为 m 可能是非质数，所以这里求逆元要用扩展欧几里得算法，求出$t_1=2,t_2=1,t_3=1$ 。
3. 代入到求解公式：$x=2*35*2+3*21*1+2*15*1=233$。
4. 而 233 只是原线性同余方程组的一个解，那么他的通解为：$x=233+k*105,k\in Z$。
5. 通过通解，我们还可以进一步求出最小的非负整数解，即当 k=-2 时， x=23 。

# 扩展中国剩余定理的推导

注意在标准的中国剩余定理上，有一个重要的前提：所有的 m 均满足两两互质。

扩展中国剩余定理可以在不满足这个重要条件下，仍然求出 最小的非负整数x 。

# 公式推导

1. 先只看前两个方程：

$$\left\{\begin{matrix} x\equiv a_1 (\bmod m_1) \\ x\equiv a_2 (\bmod m_2)\\ \end{matrix}\right.$$

2. 把模数运算转换为四则运算：

$$\left\{\begin{matrix} x=k_1*m_1+a_1\\ x=k_2*m_2+a_2\\ \end{matrix}\right.$$

3. 联立两个公式，得到：$k_1*m_1+a_1=k_2*m_2+a_2$ 。

4. 移项，得到：$k_1m_1-k_2m_2=a_2-a_1$ 。

5. 也就是：$k_1m_1+k_2(-m_2)=a_2-a_1$ 。如此，我们就把公式转换成了扩展欧几里德算法的样式。

6. 如标准中国剩余定理中的推导一样，使用扩展欧几里德找出一组解$k^\prime_1, k^\prime_2$ ，使得$k^\prime_1*m_1+k^\prime_2*(-m_2)=gcd(m_1, -m_2)$ 。

7. 此时的无解条件，就是$gcd(m_1, -m_2)$ 无法整除$a_2 - a_1$ 。（参考前置知识线性同余方程的无解条件）

8. 假设，$gcd(m_1, -m_2)=d, (a_2-a_1)/d=y$ ，此时，显然只要把$k^\prime_1, k^\prime_2$ 同时扩大 y 倍，就能得到$k_1, k_2$ 。

9. 根据线性同余方程的通解，我们知道一个重要的性质，即：
   $\left\{\begin{matrix} k_1=k^\prime_1+k*\frac{m_2}{d} \\ k_2=k^\prime_2+k*\frac{m_1}{d}\\ \end{matrix}\right.$
   当 k 为任意整数时，新的$k_1,k_2$ 仍然满足公式$k_1m_1+k_2(-m_2)=a_2-a_1$ 。

   此处的证明：

   1. 将新的 $k_1,k_2$ 带入到公式中，得到：$(k^\prime_1+k*\frac{m_2}{d})*m_1+(k^\prime_2+k*\frac{m_1}{d})*(-m_2)=a_2-a_1$
   2. 将括号展开：$k^\prime_1*m_1+k^\prime_2*(-m_2)+k*\frac{m_2*m_1}{d}-k*\frac{m_1*m_2}{d}=a_2-a_1$
   3. 消去同加同减，得到：$k^\prime_1*m_1+k^\prime_2*(-m_2)=a_2-a_1$
   4. 该公式本质与原公式是一样的，因此步骤 9 的性质成立。

10. 把上面得到的新$k_1,k_2$ 带入到原始方程组：

    $$\begin{array}{c} x = k_1 m_1 + a_1 = ( k ^ \prime_1 + k * \frac{m_2}{d} ) * m_1 + a_1 \\ = m_1 * k ^ \prime_1 + a_1 + k * \frac{m_2m_1}{d} \end{array}$$

11. 上面公式的前半部分$m_1*k^\prime_1+a_1$ ，全部是已知的，也就是这部分可以看成一个新的整数，我们记作$x_0$；后面部分的$\frac{m_2m_1}{d}$ 则是$m_2m_1$ 的最小公倍数，也是一个确定的数，我们记作$m_0$ 。

    那么，上述公式可以写成：$m_1*k^\prime_1+a_1+k*\frac{m_2m_1}{d}=x_0+k*m_0$ 。

12. 所以我们得到了前两个方程的通解：$k*m_0+a_0$ 。

13. 可以看到该通解与原方程组中的方程非常相似。因此，我们使用这种方式两两合并，最后就可以合并出整个方程组的通解。

# Code

输入格式
第 1 行包含整数 n。
第 2…n+1 行：每 i+1 行包含两个整数 ai 和 mi，数之间用空格隔开。

输出格式
输出最小非负整数 x，如果 x 不存在，则输出 −1。
如果存在 x，则数据保证 x 一定在 64 位整数范围内。

输入样例
2
8 7
11 9

输出样例
31

#include <iostream>

using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y) {

    if (!b) {

        x = 1, y = 0;

        return a;

    }

    int d = exgcd(b, a % b, y, x);

    y -= a / b * x;

    return d;

}

int main() {

    int n;

    cin >> n;

    LL m1, a1;

    cin >> m1 >> a1;

    bool has_answer = true;

    for (int i = 0; i < n - 1; i ++ ) {

        LL m2, a2;

        cin >> m2 >> a2;

        LL k1, k2;

        LL d = exgcd(m1, m2, k1, k2);  // 步骤 6

        // 步骤 7， 无解判断

        if ((a2 - a1) % d) {

            has_answer = false;

            break;

        }

        k1 *= (a2 - a1) / d;  // 步骤 9，得到新的 k1

        LL t = m2 / d;

        //k1 % t 让新 k1 变成最小，如此做是为了变成非负的。

        k1 = (k1 % t + t) % t;

        a1 = m1 * k1 + a1;  // 步骤 11，得到新的 a1

        m1 = abs(m1 / d * m2);  // 步骤 11，得到新的 m1

    }

    if (has_answer) {

        // 最后方程组变成一个方程 计算 x 的值

        cout << (a1 % m1 + m1) % m1 << endl;

    }

    else puts("-1");

    return 0;

}

END