我尝试实现中国剩余定理，为此我应该找到一些数字的乘法逆。函数正常工作，但如果它在 while 循环之后工作，则会产生错误的结果。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
main(){
int rem[5],div[5],fac[5];
int t = 0;
int c = 0;
int m = 1;
int d = 0;
void inverse(int,int);
//take remainder and divider from user
while ((rem[t] != -1) & (div[t] != -1))
{
printf("Enter remainder and divider in an order(-1 -1 to finish):");
scanf_s("%d" "%d", &rem[t], &div[t]);
if (rem[t] != -1 & div[t] != -1)
t++;
else {
printf("You ask to stop! Thank you.\n");
div[t] = -1;
rem[t] = -1;
}
}
while ((div[c] != -1) & (rem[c] != -1)) {/* print until face null character */
printf("%d . character is %d and %i\n", c + 1,rem[c], div[c]);
m = m*div[c];
c++;
}
printf(" m is %d\n", m);
//implement crt algorithm
while ((div[d] != -1) & (rem[d] != -1)) {
fac[d] = m/div[d];
printf(" m(%d) is %d\n",d+1, fac[d]);
inverse(div[d], fac[d]);
d++;
}
inverse(5,21);//this lines works if I first enter -1 -1
inverse(7,15);
system("pause");
//return 0;
}
//this is for finding gcd and inverse
int a, b, i;
int k = 1;
int q[10];
int r[10];
int x[10];
int y[10];
void inverse(int a, int b){
q[1] = (a / b);
r[1] = a%b;
q[0] = a;
r[0] = b;
//find gcd of two numbers
while (r[k] != 0){
k = k++;
q[k] = r[k - 2] / r[k - 1];
r[k] = r[k - 2] % r[k - 1];
}
printf("gcd of %d and %d is: %d\n", a, b, r[k - 1]);
//check whether these two numbers are relatively prime,if it is then find inverse
if (r[k - 1] != 1)
printf("These two numbers should be relatively prime\n");
else{
x[k - 1] = -q[k - 1];
y[k - 1] = 1;
i = k - 1;
while (i > 1){
x[i - 1] = -x[i] * q[i - 1] + y[i];
y[i - 1] = x[i];
i = i - 1;
}
//check whether the inverse of number is less than 0, if it is then add the modulo
if ((x[1] % a) < 0)
printf("multiplicative inverse of %d in mod %d is %d\n", b, a, (x[1] % a) + a);
else
printf("multiple inverse of %d in mod %d is %d\n", b, a, x[1] % a);
}
}