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

以下是C语言实现中国剩余定理的代码：

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

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

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

// 求逆元
int inverse(int a, int b)
{
int t = 0, newt = 1;
int r = b, newr = a;

while (newr != 0)
{
int q = r / newr;

int temp = t;
t = newt;
newt = temp - q * newt;

temp = r;
r = newr;
newr = temp - q * newr;
}

if (r > 1)
return -1;
if (t < 0)
t += b;

return t;
}

// 求解中国剩余定理
int chinese_remainder(int *a, int *m, int n)
{
int M = 1;
for (int i = 0; i < n; i++)
M *= m[i];

int x = 0;
for (int i = 0; i < n; i++)
{
int Mi = M / m[i];
int ti = inverse(Mi, m[i]);

x = (x + a[i] * ti * Mi) % M;
}

return x;
}

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

int x = chinese_remainder(a, m, n);

printf("x = %d\n", x);

return 0;
}