问一道开关电灯的acm题目

开关电灯
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
N盏灯排成一排,从1到N依次编号。有N个人也同样编号。
第一个人将灯全部熄灭;
第2个人将对应2和2的倍数的灯打开;
第3个人将对应着3和3的倍数的灯做反向操作(如果原来是开,则关掉它,否则就打开它);
以后的人和3做同样的操作,即第i个人将对应着i和i的倍数的灯做反向操作。
输入
灯的总数N, 1<=N<=1000
输出
在第N个人操作后,顺序输出还亮着灯的编号。
样例输入
8
样例输出
2 3 5 6 7 8

acm

6个回答

http://www.docin.com/p-687654793.html
稍微修改下就是C语言了。
这题目不是acm的,属于初级难度的。

有n盏灯排成一排,依次标号1,2,…,n,每盏灯都有一根拉线开关,最初电灯都是关着的.现有n个人,都沿着电灯路线走过,第一个人走过时,把凡是号码是1的倍数的灯的开关拉一下;接着第二个人走过时,把凡是号码是2的倍数的灯的开关拉一下;第三个走过时,把凡是号码是3的倍数的灯的开关拉一下;…;最后,第n个人走过时,把最后那盏灯的开关拉一下.
答案:
由于最初所有电灯是关着的,所以只有哪些拉了奇数次开关的电灯才是亮的,而每一盏电灯的拉线开关被拉了多少次取决于这盏灯的编号的数字有多少个不同的正约数,最后亮着的灯的编号只有为完全平方数.所以,n=10时,只有编号为1,4,9亮着,
由于最初所有电灯是关着的,所以只有哪些拉了奇数次开关的电灯才是亮的,而每一盏电灯的拉线开关被拉了多少次取决于这盏灯的编号的数字有多少个不同的正约数,最后亮着的灯的编号只有为完全平方数.所以,n=20时,只有编号为1,4,9,16亮着;
这个题目 不要用暴力破解法做,它是一个有点考验智力的题目,你如果 能理解好了,比你上面的答案还好。~~

这个题目还经常会出现在一些笔试题目 中~~

只有平方数会熄灭。
将问题简化,对于每一个灯的亮暗状态我们只需要知道按了多少次。
简单思考后我们可以知道对于编号为x的灯,它被按的次数是它的约数个数。
而其中只有平方数的约数是奇数个。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问