高祖刘邦问韩信统御士兵多少,韩信答说,每3人一列余1人,5人一列余2人,7人一列余4人,13人一列余6人……刘邦茫然而不知其数。 请求出满足要求的前N个韩信统御的士兵数量。 输入 正整数N,1=<N<100, 输出 前N个韩信统御的士兵数量C++
时间: 2024-03-24 10:35:46 浏览: 64
以下是使用扩展欧几里得算法求解同余方程组的 C++ 代码,可以求出前 N 个满足条件的士兵数量:
```c++
#include <iostream>
#include <vector>
using namespace std;
// 扩展欧几里得算法,求 ax + by = gcd(a, b) 的一组解
void exgcd(int a, int b, int &x, int &y, int &gcd) {
if (b == 0) {
x = 1;
y = 0;
gcd = a;
return;
}
exgcd(b, a % b, y, x, gcd);
y -= a / b * x;
}
// 求解同余方程组 x ≡ r[i] (mod m[i])
int chinese_remainder(const vector<int> &m, const vector<int> &r) {
int n = m.size();
int M = 1;
for (int i = 0; i < n; i++) {
M *= m[i];
}
int x = 0;
for (int i = 0; i < n; i++) {
int Mi = M / m[i];
int xi, yi, gcd;
exgcd(Mi, m[i], xi, yi, gcd);
x += r[i] * xi * Mi;
}
return (x % M + M) % M;
}
int main() {
int n;
cin >> n;
vector<int> m = {3, 5, 7, 13};
vector<int> r = {1, 2, 4, 6};
int x = chinese_remainder(m, r);
int M = 1;
for (int i = 0; i < m.size(); i++) {
M *= m[i];
}
for (int i = 0; i < n; i++) {
cout << x << endl;
x += M;
}
return 0;
}
```
这份代码中,exgcd 函数实现了扩展欧几里得算法,chinese_remainder 函数实现了求解同余方程组的过程。在 main 函数中,先定义了条件中的模数和余数,然后调用 chinese_remainder 函数求解出一个满足所有条件的士兵数量 x,再通过循环求出前 N 个满足条件的士兵数量。
阅读全文
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20250102104920.png)
![application/pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![docx](https://img-home.csdnimg.cn/images/20241231044901.png)
![DOC](https://img-home.csdnimg.cn/images/20250102104920.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![ppt](https://img-home.csdnimg.cn/images/20241231044937.png)
![docx](https://img-home.csdnimg.cn/images/20241231044901.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![pdf](https://img-home.csdnimg.cn/images/20241231044930.png)
![docx](https://img-home.csdnimg.cn/images/20241231044901.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)