中国剩余定理——C++实现

定理——C++实现"/>

中国剩余定理——C++实现

1.程序说明

输入：同余方程的个数n，各方程的参数

输出：同余方程组的解

运行结果：

与课本例题对比：

2.实现思路

• 求x模m的逆元

采用拓展欧几里得算法计算x模m的逆元，代码如下：

int ni(int x, int m) {int r[100], s[100], t[100], q[100];r[0] = x;r[1] = m;s[0] = 1;t[0] = 0;s[1] = 0;t[1] = 1;int i = 1;while (r[i] != 0) {q[i] = r[i - 1] / r[i];s[i + 1] = s[i - 1] - q[i] * s[i];t[i + 1] = t[i - 1] - q[i] * t[i];r[i + 1] = r[i - 1] % r[i];i++;}while (s[i - 1] < 0) {s[i - 1] += m;}return s[i - 1];
}//求x模m的逆元

• 中国剩余定理

获取方程组的个数以及同余方程的各个参数后，按照中国剩余定理的方式依次求出来Mi及其逆元，完成求解。

3.完整代码

#include<iostream>
using namespace std;
int ni(int x, int m) {int r[100], s[100], t[100], q[100];r[0] = x;r[1] = m;s[0] = 1;t[0] = 0;s[1] = 0;t[1] = 1;int i = 1;while (r[i] != 0) {q[i] = r[i - 1] / r[i];s[i + 1] = s[i - 1] - q[i] * s[i];t[i + 1] = t[i - 1] - q[i] * t[i];r[i + 1] = r[i - 1] % r[i];i++;}while (s[i - 1] < 0) {s[i - 1] += m;}return s[i - 1];
}//求x模m的逆元int main() {cout << "请输入方程的个数" << endl;int n;cin >> n;int* b = new int[n];int* m = new int[n];int* M = new int[n];int* x = new int[n];//存放逆元int i = 0;int sum = 1;//这里sum代表了m的值cout << "请依次输入各方程的参数" << endl;cout << "格式参考：x≡b(mod m)" << endl;for (i = 0; i < n; i++) {cout << "请输入第" << i+1 << "个方程的参数(先输入b,后输入m)" << endl;cin >> b[i] >> m[i];sum *= m[i];M[i] = 1;}for (i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i != j) {M[i] *= m[j];}}}for (i = 0; i < n; i++) {x[i] = ni(M[i], m[i]);}int ans = 0;for (i = 0; i < n; i++) {ans += x[i] * M[i] * b[i];}while (ans - sum >= 0) {ans -= sum;}cout << "该方程组的解为x≡" << ans << "(mod " << sum << ")" << endl;cin.get();cin.get();
}