c++实现中国剩余定理

中国剩余定理是数论中的重要定理，在计算机科学中也有着广泛的应用。在 C 语言中实现中国剩余定理，可以使用暴力算法或者使用扩展欧几里得算法。

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

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

// 求模运算的逆元
int mod_inverse(int a, int m)
{
    a = a % m;
    for (int x = 1; x < m; x++)
        if ((a * x) % m == 1)
            return x;
    return -1;
}

// 求解中国剩余定理的结果
int crt(int num, int *a, int *m)
{
    int M = 1;
    int sum = 0;

    for (int i = 0; i < num; i++)
        M *= m[i];

    for (int i = 0; i < num; i++) {
        int Mi = M / m[i];
        int x = mod_inverse(Mi, m[i]);
        sum += a[i] * x * Mi;
    }

    return sum % M;
}

int main()
{
    int num = 3;
    int a[] = { 2, 3, 2 };
    int m[] = { 3, 5, 7 };

    int result = crt(num, a, m);
    printf("Result: %d\n", result);

    return 0;
}

在上面的代码中，我们使用了求模运算的逆元来求解中国剩余定理，最终通过循环遍历所有的方程，并将它们的结果相加，最终得到中国剩余定理的结果。