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

以下是一个用C语言实现中国剩余定理的示例代码：

#include <stdio.h>

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

int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}

int inv(int a, int b)
{
    int r1 = a, r2 = b, t1 = 0, t2 = 1, q, r, t;
    while (r2 > 0)
    {
        q = r1 / r2;
        r = r1 - q * r2;
        t = t1 - q * t2;
        r1 = r2;
        r2 = r;
        t1 = t2;
        t2 = t;
    }
    if (r1 == 1)
    {
        if (t1 < 0) t1 += b;
        return t1;
    }
    else
    {
        return -1;
    }
}

int main()
{
    int n, i, lcm_val = 1, x, a, b, m, M = 0, Mi, ans = 0;

    printf("Enter the number of equations: ");
    scanf("%d", &n);

    int b_vals[n], m_vals[n], Mi_vals[n], x_vals[n];

    for (i = 0; i < n; i++)
    {
        printf("Enter b%d and m%d: ", i + 1, i + 1);
        scanf("%d %d", &b, &m);
        b_vals[i] = b;
        m_vals[i] = m;
        lcm_val = lcm(lcm_val, m);
        M += b * (lcm_val / m);
    }

    for (i = 0; i < n; i++)
    {
        Mi = lcm_val / m_vals[i];
        Mi_vals[i] = Mi;
        x = inv(Mi, m_vals[i]);
        x_vals[i] = x;
        ans += b_vals[i] * x * Mi;
    }

    printf("The solution is: %d (mod %d)\n", ans % lcm_val, lcm_val);

    return 0;
}

该代码首先读取用户输入的方程组的数量，并在循环中读取每个方程的b和m值。然后，使用lcm函数计算m的最小公倍数，并计算M的值。接下来，使用inv函数计算每个Mi和它的逆元x，并将它们存储在数组中。最后，计算答案并输出结果。

注意，该实现假设方程组中的每个m值是互质的。如果方程组中的m值不是互质的，则需要进行扩展中国剩余定理的计算。