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

中国剩余定理

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

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

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

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

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

如何求出未知数x呢？

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

举个例子

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

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

扩展中国剩余定理的推导

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

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

公式推导

1. 先只看前两个方程：
   

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

3. 联立两个公式，得到： 。

4. 移项，得到： 。

5. 也就是： 。如此，我们就把公式转换成了扩展欧几里德算法的样式。

6. 如标准中国剩余定理中的推导一样，使用扩展欧几里德找出一组解 ，使得 。

7. 此时的无解条件，就是 无法整除 。（参考前置知识线性同余方程的无解条件）

8. 假设， ，此时，显然只要把 同时扩大y倍，就能得到 。

9. 根据线性同余方程的通解，我们知道一个重要的性质，即：
   

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

   此处的证明：

   1. 将新的 带入到公式中，得到：
   2. 将括号展开：
   3. 消去同加同减，得到：
   4. 该公式本质与原公式是一样的，因此步骤9的性质成立。

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

11. 上面公式的前半部分 ，全部是已知的，也就是这部分可以看成一个新的整数，我们记作 ；后面部分的 则是 的最小公倍数，也是一个确定的数，我们记作 。

    那么，上述公式可以写成： 。

12. 所以我们得到了前两个方程的通解： 。

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