神犇营-44-开关灯

【小韦同学@神犇营-44-开关灯】

题目：

描述

假设有N盏灯(N为不大于5000的正整数)，从1到N按顺序依次编号，初始时全部处于开启状态；有M个人(M为不大于N的正整数)也从1到M依次编号。
第一个人（1号）将灯全部关闭，第二个人（2号）将编号为2的倍数的灯打开，第三个人（3号）将编号为3的倍数的灯做相反处理（即，将打开的灯关闭，将关闭的灯打开）。依照编号递增顺序，以后的人都和3号一样，将凡是自己编号倍数的灯做相反处理。
请问：当第M个人操作之后，哪几盏灯是关闭的，按从小到大输出其编号，其间用逗号间隔。

输入

输入正整数N和M，以单个空格隔开。

输出

顺次输出关闭的灯的编号，其间用逗号间隔。

输入样例1

10 10

输出样例1

1,4,9

题解：

/*********************************************************************

* 题目：神犇营-44-开关灯
* 作者：小韦同学
* 邮箱：[email protected]

* 题解：
	思路：
	用一个数组作为标记数组，false 表示对应的灯的状态是灭的，true 表示
	灯的状态的亮着的。初始化为 false。 
	首先将编号为 2 的倍数的灯打开（标记数组对应置为 true）。
	其次从编号为3的灯开始，将它们编号倍数的灯置为相反状态：开的灯变灭，
	灭着的灯打开（标记数组为 false 置为 true，true 置为 false）。 
	最后输出标记数组的的值为 false 的对应的下标即可。 
	注意：
	两个灯的编号之间用逗号隔开，最后一个编号后无逗号。 
	
*********************************************************************/

#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 10;
// 标记数组，下标表示灯的编号，值为fasle表示该灯灭，true表示灯亮
bool light[N];   

int main() {

	int n, m;
	cin >> n >> m;
	
	// 编号为2的倍数的灯打开，标记数组置为true 
	for (int i = 2; i <= n; i += 2) {
		light[i] = true;
	}
	// 从编号为3的灯开始，将它们编号倍数的灯置为相反状态 
	for (int i = 3; i <= m; i++) {
		for (int j = i; j <= n; j = j + i) {
			if (light[j]) light[j] = false;
			else light[j] = true;
		}
	}

	cout << 1;  // 先将1输出，因为编号为1的灯一定是关闭的 
	for (int i = 2; i <= n; i++) {
		if (!light[i]) {
			if (i != 1) cout << ",";  // 除了第1个，前面输出逗号 
			cout << i;
		}
	}
	return 0;

}

我是小韦同学，企者不立，跨者不行，每天进步一点点。
欢迎大家多多交流，如果发现有错误，请多指正。有疑问的同学也可以留言评论或者发邮件。
邮箱：[email protected]