自己做一个网站湖南移动网站建

1109：开关灯 时间限制: 1000 ms    内存限制: 65536 KB

【题目描述】

假设有N盏灯(N为不大于5000的正整数)，从1到N按顺序依次编号，初始时全部处于开启状态；有M个人(M为不大于N的正整数)也从1到M依次编号。

第一个人(1号)将灯全部关闭，第二个人(2号)将编号为2的倍数的灯打开，第三个人(3号)将编号为3的倍数的灯做相反处理(即将打开的灯关闭，将关闭的灯打开)。依照编号递增顺序，以后的人都和3号一样，将凡是自己编号倍数的灯做相反处理。

请问：当第M个人操作之后，哪几盏灯是关闭的，按从小到大输出其编号，其间用逗号间隔。

【输入】

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

【输出】

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

【输入样例】

10 10

【输出样例】

1,4,9

说明

主要考查一维数组和循环嵌套。

此处将使用两种算法解决。第一种是模拟法，较为简单；第二种是筛选法，较为优秀。

关于筛选法的基本思想，可参考文章：

【信奥·数论】求区间质数(素数)的算法(进阶篇)

题目概述

编号1~M(M<=N)个人操作编号为1~N(N<=5000)盏灯，1号把N盏灯全关，从2号开始，如果灯的编号是人编号的倍数，作相反的处理，即原来是关的就打开，原来是开的就关闭。

到第M个人操作完成后，最后输出N盏灯中关闭的编号。

思路分析(方法1，适合入门)

以题目输入输出样例为例，下图橙色背景数字是打开的灯，灰色背景是关闭的灯，该数字表示灯的编号。其中红色数字表示要作相反处理的灯号。

图中的这一过程不难理解。M个人可以循环M次，而每个人对N盏灯中相关的灯进行相反操作，可以循环N次。很明显，使用循环嵌套的框架即可。

M个人中，每个人都对N盏灯进行遍历和相反操作，所以M个人的循环作为外层，而N盏灯的循环作为内层。循环嵌套代码框架如下：

灯有两个状态(开/关)，即有两个值，且每个人都对灯进行操作，所以N盏灯肯定需要使用一维数组存储。

N盏灯的编号从1开始，对应数组下标为1的元素，所以数组下标为0的元素不使用，从下标1开始使用，方便写代码。如果N=5000，那么最后一盏灯的下标是5000。如果数组下标为5000的元素，那么声明数组时，数组的长度不能小于5001。所以声明如下变量和数组：

第1个人关闭所有灯，从第2个人开始才是以倍数的形式操作。所以，将数组的所有元素初始化为一个数，表示关灯状态。而数组在声明时只能初始化所有元素为0。所以，将数组a所有元素初始化为0，表示所有灯初始状态是关闭的，而灯打开的状态可以用数字1表示。将声明数组a的代码修改如下：

如此一来，数组a就初始化所有元素的值为0，其中{0}中的数字0可以省略。

上面讲到，第1个人关闭所有灯，而数组a已经把所有元素初始化为0(关闭状态)。所以，外层循环直接从第2个人开始，修改循环嵌套代码如下，变量i代表人的编号，变量j代表灯的编号：

接着在循环嵌套中开始为2~M个人对N盏灯进行处理。如果灯号j是i的倍数，将对应灯号作相反处理，即对数组a[j]的值进行相反的操作。如果a[j]等于1，那么将a[j]赋值为0，否则将a[j]赋值为1。代码如下：

循环结束后，使用一个循环遍历数组a的N个元素，即看看N盏灯中，有哪些是关闭的。如果a[i]等于0，说明是关闭的，输出该灯的编号，即该元素的下标值，代码如下：

不过这是不对的，因为相邻两个灯号之间要输出一个逗号。修改代码如下：

还是不正确，输出结果是【1,4,9,】，最后多了一个逗号。输出时不管逗号写在变量i的前面还是后面，输出结果都多了一个逗号。

其实可以这么思考：最终输出结果的逗号比数字少一个，而输出时，数字和逗号是同时输出的，所以逗号和数字的数目相等，如果能确定第一或最后一盏关闭的灯的编号，就很简单了。但最后一盏关闭的灯的编号是不能确定的，而第一盏灯肯定是关闭的，所以先输出第一盏灯的编号，然后再循环输出剩余的逗号和灯号。代码如下：

问：为什么第一盏灯肯定是关闭呢？

答：所有灯初始时关闭的(第1个人全部关闭)，从第2个人开始，不可能存在是1的整数倍的正整数，那么就无法对第一盏灯进行操作。

数据类型：存储5000盏灯的一维数组可以在main函数中声明，也可以声明为全局。N最大是5000，而M不大于N，说明M最大也是5000。所有数据选择int类型即可。

完整代码：

思路分析(方法2，适合基础和思维较好的同学)

在方法1的基础上进行优化。

方法1的循环嵌套代码框架：

其实没有必要每个人都从第1盏灯开始遍历，从第i盏灯开始即可。因为第i个人是从第i盏灯开始操作(i以内的数字都不是i的倍数)，所以内层循环int j = 1可以改为int j = i。

同样，第i个人只对i的倍数的灯进行操作，所以内层循环的更新操作(j++)可以改为j += i。

修改后的代码：

对第j盏灯是否为第i个人的倍数，以及对灯进行相反的操作也可以进行优化。

方法1代码：

因为现在的循环已修改，每次循环都是i的倍数(即遍历的灯号都是人编号的倍数)，所以语句【if (j % i == 0)】可以删掉。

进行相反操作时，因为a[j]的值要么为1，要么为0，只要把a[j]的值进行逻辑非运算即可。例如a[j]的值为1，那么!a[j]的值为0。也可以写成【a[j]=1-a[j]】，如果a[j]等于1，那么1-a[j]等于0；如果a[j]等于0，那么1-a[j]等于1。

代码如下，二选一：

完整代码：

思路分析(方法3，筛选法，适合思维更好的同学)

完整代码：

此方法与方法2的思路相似，都是按倍数来遍历。

代码中，变量j是倍数，从1倍开始，每次循环递增1。j是原来的灯号，经过i倍筛选，即可完成开关灯操作。

关于筛选法的基本思想，可以参考下面文章，在此不再赘述。

【信奥·数论】求区间质数(素数)的算法(进阶篇)

三种方法的运行时间

方法1：

方法2：

方法3：

重难点

三种方法中，方法2和方法3的运行时间看似相当，实际上方法2是最快的，而方法3的思路值得学习。

本题的难点是循环的嵌套框架，即思路。以及最后输出的技巧。

如果能独自完成，说明自己对循环嵌套和一维数组掌握得相当不错。

对于数组类型的选择，可以选择bool类型，空间开销较int类型的小。

参考代码下载链接

https://pan.baidu.com/s/123L9UFBoUaNnWAZwFiVv6A 

提取码：dsbc

END

注：题目来源于网络，转载于《信息学奥赛一本通(C++版)在线评测系统》，点击下方的【阅读原文】即可打开该题的链接。

题解属于本微信公众号【大神编程】原创。