要可以由使用者輸入
时间: 2024-02-22 17:58:18 浏览: 16
好的,那么可以按照以下方式修改代码,让用户可以输入模方程组中的余数和模数:
```c++
#include <iostream>
using namespace std;
// 求 a 和 b 的最大公约数
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
// 求 a 和 b 的最小公倍数
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
// 求逆元
int inv(int a, int m) {
int x, y;
int d = gcd(a, m);
if (d == 1) {
// 如果 a 和 m 互质,则存在逆元
x = 1;
y = 0;
while (a > 0) {
int q = m / a;
int t = m % a;
m = a;
a = t;
int tmp = x - q * y;
x = y;
y = tmp;
}
return x < 0 ? x + m : x;
} else {
// 如果 a 和 m 不互质,则不存在逆元
return -1;
}
}
// 中国剩余定理
int CRT(int a[], int m[], int n) {
int M = 1;
for (int i = 0; i < n; i++) {
M = lcm(M, m[i]); // 求所有模数的最小公倍数
}
int x = 0;
for (int i = 0; i < n; i++) {
int Mi = M / m[i];
int ti = inv(Mi, m[i]);
x = (x + a[i] * Mi * ti) % M;
}
return x;
}
int main() {
int n;
cout << "请输入模方程组的个数 n:";
cin >> n;
int a[n], m[n];
cout << "请依次输入模方程组中的余数 a 和模数 m:" << endl;
for (int i = 0; i < n; i++) {
cin >> a[i] >> m[i];
}
int x = CRT(a, m, n); // 求解同余方程组
cout << "模方程组的解为:x = " << x << endl;
return 0;
}
```
这样修改后,程序运行时会先要求用户输入模方程组的个数 n,然后依次输入每个模方程组的余数 a 和模数 m。最后输出模方程组的解。