c++实现中国剩余定理

中国剩余定理是一种数论定理，它描述了在模意义下的多项式方程的解。在 C 语言中，可以使用暴力枚举法来实现中国剩余定理。

具体实现方法如下：

1. 输入所有的模数 mi 和余数 ai。
2. 从 0 到所有模数的积中枚举 x 的值。
3. 对于每一个 x，判断是否满足所有方程，即 x ≡ ai (mod mi)。
4. 如果找到一个满足所有方程的 x，则输出 x 并退出程序。

以下是 C 语言代码的实现：

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int CRT(int n, int *a, int *m) {
    int M = 1, x = 0;
    for (int i = 0; i < n; i++) {
        int a_ = (a[i] - x) % m[i];
        if (a_ < 0) a_ += m[i];
        int c = m[i] / gcd(M, m[i]);
        int y, d = exgcd(M, m[i], y, c);
        if (a_ % d) return -1;
        c *= a_ / d;
        x += c * M;
        M *= m[i] / d;
        x = (x % M + M) % M;
    }
    return (x % M + M) % M;
}

int main() {
    int n, a[100], m[100];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &m[i], &a[i]);
    }
    int x = CRT(n, a, m);
    if (x == -1) {