用C++解答中国剩余定理

中国剩余定理（Chinese Remainder Theorem）是一个求解一组同余方程的方法，假设给定一组同余方程：

x ≡ a1 (mod m1) x ≡ a2 (mod m2) ... x ≡ an (mod mn)

其中ai和mi分别为整数，mi之间互质。中国剩余定理可以求解出满足这组同余方程的x的唯一解。

下面是用C++实现中国剩余定理的代码：

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

// 求解最大公约数
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// 求解乘法逆元
int modInverse(int a, int m) {
    int m0 = m;
    int y = 0, x = 1;

    if (m == 1) {
        return 0;
    }

    while (a > 1) {
        int q = a / m;
        int t = m;

        m = a % m, a = t;
        t = y;

        y = x - q * y;
        x = t;
    }

    if (x < 0) {
        x += m0;
    }

    return x;
}

// 使用中国剩余定理求解同余方程组
int chineseRemainderTheorem(const vector<int>& a, const vector<int>& m) {
    int M = accumulate(m.begin(), m.end(), 1, multiplies<int>());
    int x = 0;

    for (int i = 0; i < m.size(); i++) {
        int Mi = M / m[i];
        x += a[i] * Mi * modInverse(Mi, m[i]);
    }

    return x % M;
}

int main() {
    // 示例：解同余方程组 x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
    vector<int> a = {2, 3, 2};
    vector<int> m = {3, 5, 7};

    int x = chineseRemainderTheorem(a, m);
    cout << "x = " << x << endl;

    return 0;
}

运行上述代码，输出结果为 x = 23，即满足给定同余方程组的唯一解为23