假设有N盏灯(N为不大于5000的正整数),从1到N按顺序依次编号,初始时全部处于开启状态;有M个人(M为不大于 N的正整数)也从1到M依次编号。 第一个人(1号)将灯全部关闭,第二个人(2号)将编号为2的倍数的灯打开,第三个人(3号)将编号为3的倍数的灯做相反处理(即,将打开的灯关闭,将关闭的灯打开)。依照编号递增顺序,以后的人都和3号一样,将凡是自己编号倍数的灯做相反处理。 请问:当第M个人操作之后,哪几盏灯是关闭的,按从小到大输出其编号,其间用逗号间隔。 输入 输入正整数N和M,以单个空格隔开。 输出 顺次输出关闭的灯的编号,其间用逗号间隔。 样例输入 10 10 样例输出 1,4,9 使用c++代码编写
时间: 2024-04-12 21:27:14 浏览: 262
以下是用C++编写的解答代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
vector<int> getClosedLights(int N, int M) {
vector<bool> lights(N + 1, true); // 初始时所有灯都是开启状态
for (int i = 2; i <= M; i++) {
for (int j = 1; j <= N; j++) {
if (j % i == 0) {
lights[j] = !lights[j]; // 将倍数为i的灯进行相反处理
}
}
}
vector<int> closedLights;
for (int i = 1; i <= N; i++) {
if (!lights[i]) {
closedLights.push_back(i); // 将关闭的灯的编号添加到结果中
}
}
return closedLights;
}
int main() {
int N, M;
cin >> N >> M;
vector<int> result = getClosedLights(N, M);
for (int i = 0; i < result.size(); i++) {
cout << result[i];
if (i != result.size() - 1) {
cout << ",";
}
}
cout << endl;
return 0;
}
```
这段代码首先定义了一个函数 `getClosedLights`,用于计算第M个人操作之后关闭的灯的编号。算法思想是使用一个布尔类型的数组 `lights` 来表示每盏灯的状态,初始时都为开启状态。然后从第2个人开始,依次遍历每个人,对应将倍数为当前人数的灯进行相反处理。最后遍历数组,将关闭的灯的编号添加到结果中。
在 `main` 函数中,读取输入的N和M,调用 `getClosedLights` 函数获得结果,并按要求输出。
希望能对你有帮助!
阅读全文