用c写一个中国剩余定理

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

#include <stdio.h>

int gcd(int a, int b) {
if (b == 0) {
return a;
}
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 k) {
int prod = 1, i, sum = 0;
for (i = 0; i < k; i++) {
prod *= num[i];
}
for (i = 0; i < k; 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 k = sizeof(num) / sizeof(num[0]);
printf("x = %d\n", chinese_remainder(num, rem, k));
return 0;
}

这个程序实现了中国剩余定理，可以计算出满足以下条件的 x 的值：

x ≡ 2 (mod 3)
x ≡ 3 (mod 4)
x ≡ 1 (mod 5)

如果你有其他编程问题，欢迎继续提问。