用C语言编程实现计算同余式ax≡b(mod m)的解

#include <stdio.h>

int main() {
int a, b, m, x, y;
printf("Enter values for a, b, and m: ");
scanf("%d %d %d", &a, &b, &m);

// 扩展欧几里得算法求解ax+my=gcd(a,m)的解(x,y)
int r1 = a, r2 = m, s1 = 1, s2 = 0, t1 = 0, t2 = 1, q, r, gcd;
while (r2 > 0) {
q = r1 / r2;
r = r1 - q * r2;
r1 = r2;
r2 = r;

int temp = s1 - q * s2;
s1 = s2;
s2 = temp;

temp = t1 - q * t2;
t1 = t2;
t2 = temp;
}
gcd = r1;
x = s1;
y = t1;

if (b % gcd != 0) {
printf("The congruence is inconsistent.\n");
} else {
int x0 = x * (b / gcd);
printf("The general solution is x = %d + %d*k\n", x0, m / gcd);
}

return 0;
}