中国剩余定理c++

中国剩余定理（Chinese Remainder Theorem）是一种求解同余方程组的方法，可以用于解决一些数学和计算机科学问题。

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

#include <iostream>
using namespace std;

// 求 a 和 b 的最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 求 a 和 b 的最小公倍数
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

// 求逆元
int inv(int a, int m) {
    int x, y;
    int d = gcd(a, m);
    if (d == 1) {
        // 如果 a 和 m 互质，则存在逆元
        x = 1;
        y = 0;
        while (a > 0) {
            int q = m / a;
            int t = m % a;
            m = a;
            a = t;
            int tmp = x - q * y;
            x = y;
            y = tmp;
        }
        return x < 0 ? x + m : x;
    } else {
        // 如果 a 和 m 不互质，则不存在逆元
        return -1;
    }
}

// 中国剩余定理
int CRT(int a[], int m[], int n) {
    int M = 1;
    for (int i = 0; i < n; i++) {
        M = lcm(M, m[i]);  // 求所有模数的最小公倍数
    }
    int x = 0;
    for (int i = 0; i < n; i++) {
        int Mi = M / m[i];
        int ti = inv(Mi, m[i]);
        x = (x + a[i] * Mi * ti) % M;
    }
    return x;
}

int main() {
    int a[] = {2, 3, 2};
    int m[] = {3, 5, 7};
    int n = 3;
    int x = CRT(a, m, n);  // 求解同余方程组
    cout << "x = " << x << endl;
    return 0;
}

在上面的代码中，`CRT()` 函数接收三个参数：`a` 数组表示模方程组中的余数，`m` 数组表示模数，`n` 表示模方程组的个数。函数返回值是模方程组的解。

需要注意的是，该代码中求解逆元的方法是使用扩展欧几里得算法。如果模数很大，可以使用欧拉定理和扩展欧拉定理来求解。