用c编程实现计算中国剩余定理

以下是一个C程序，它实现了中国剩余定理的计算。

#include <stdio.h>
#include <stdlib.h>

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

int inverse(int a, int m) {
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;

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

    while (a > 1) {
        q = a / m;
        t = m;
        m = a % m;
        a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }

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

    return x1;
}

int chinese_remainder(int *num, int *rem, int len) {
    int prod = 1, sum = 0;
    int i, j;

    for (i = 0; i < len; i++) {
        prod *= num[i];
    }

    for (i = 0; i < len; i++) {
        int pp = prod / num[i];
        sum += rem[i] * inverse(pp, num[i]) * pp;
    }

    return sum % prod;
}

int main() {
    int num[] = {3, 4, 5};
    int rem[] = {2, 3, 1};
    int len = sizeof(num) / sizeof(num[0]);

    int result = chinese_remainder(num, rem, len);

    printf("Result: %d\n", result);

    return 0;
}

在此示例中，我们使用数组来存储模数和余数，然后调用 `chinese_remainder()` 函数来计算解。`gcd()` 函数用于计算最大公约数，`inverse()` 函数用于计算逆元素。在 `chinese_remainder()` 函数中，我们首先计算所有模数的乘积，然后使用逆元素计算出每个余数的系数，并将它们相加以获得最终结果。

这个程序的输出应该是 `Result: 23`，这是中国剩余定理的解。