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

中国剩余定理

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

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

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

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

在数论中，线性同余方程是最基本的同余方程，“线性”表示方程只有一个未知数，即形如：的方程。

如何求出未知数x呢？

根据同余的含义：，那么一定有整数y使得。
把my移动到右面，得到：。
如果我们假设，那么步骤二的方程可以写为：。
根据裴蜀定理，上面的方程有解的前提是 gcd(a,m)|b，其中|表示整除。
用扩展欧几里德算法求出一组整数，使得。
现在有两组等式：1. ；2. 。其中b又一定是gcd(a,m)的倍数，那么我们只要将等式2两面同时扩大b/gcd(a,m)倍不就能得到等式1了嘛。
扩大后就得到了。
此时的系数是1，那么我们只要把这个系数扩展到全部整数，就得到了x的通解：，其中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;
}

标准中国剩余定理的推导

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

对于问题，若其中满足两两互质，则可以使用标准的中国剩余定理求解，形如：

「求解公式」

其中， (也就是除了以外的个数的乘积) ，为的逆元。即，。

公式证明

在上面公式的基础上左右两面同时乘以，得到：。

又因为当时，每个中都被乘了一个（没明白的，再看一遍的定义），所以有。

所以当i=1时，对于求解公式中的每一项除了之外，全部是。所以有，那么当i取其他值时候同理。这样我们就证明了最终的线性同余方程组的求解公式，也就是中国剩余定理。

举个例子

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

首先把例子给的值对应到模型上，其中，。
首先算出M，，再依次求出，，算出的逆元，其中因为m可能是非质数，所以这里求逆元要用扩展欧几里得算法，求出。
代入到求解公式：。
而233只是原线性同余方程组的一个解，那么他的通解为：。
通过通解，我们还可以进一步求出最小的非负整数解，即当k=-2时，x=23。

扩展中国剩余定理的推导

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

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

公式推导

先只看前两个方程：
把模数运算转换为四则运算：
联立两个公式，得到：。
移项，得到：。
也就是：。如此，我们就把公式转换成了扩展欧几里德算法的样式。
如标准中国剩余定理中的推导一样，使用扩展欧几里德找出一组解，使得。
此时的无解条件，就是无法整除。（参考前置知识线性同余方程的无解条件）
假设，，此时，显然只要把同时扩大y倍，就能得到。
根据线性同余方程的通解，我们知道一个重要的性质，即：

当k为任意整数时，新的仍然满足公式。

此处的证明：
1. 将新的带入到公式中，得到：
2. 将括号展开：
3. 消去同加同减，得到：
4. 该公式本质与原公式是一样的，因此步骤9的性质成立。
把上面得到的新带入到原始方程组：
上面公式的前半部分，全部是已知的，也就是这部分可以看成一个新的整数，我们记作；后面部分的则是的最小公倍数，也是一个确定的数，我们记作。

那么，上述公式可以写成：。
所以我们得到了前两个方程的通解：。
可以看到该通解与原方程组中的方程非常相似。因此，我们使用这种方式两两合并，最后就可以合并出整个方程组的通解。

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