自动搬运

查看原文

来自洛谷，原作者为

	BlueArc **

搬运于2025-08-24 21:31:22，当前版本为作者最后更新于2017-01-21 16:48:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看了看别人的题解，都是枚举小于n的完全平方数输出，代码极为简单，因此本人不再给出代码。

下证明为什么是完全平方数：

首先，你要知道，对于每一个数n，除非它是完全平方数，否则它一定有偶数个因子。

因为如果i是n的因子，那么n/i也一定是n的因子。例如当n=20时，i=4是20的因子，那么n/i=5也是20的因子

这样，n的因子都是成对出现的，所以n有偶数个因子

但是，有一种特殊情况，即n/i=i。例如4/2=2。由于i和n/i是同一个数，算因子只能是一个，这时n的因子就是奇数个

把n/i=i变形，得n=i*i，即n是完全平方数，所以只有完全平方数有奇数个因子

对于本题，由于灯只有两种状态(开或关,可类比于奇数和偶数),而初始状态是关的

而每个灯泡如果能被人的编号整除，状态就会变化。

把整个过程看成一个整体，也就是只有这一盏灯的因数的编号的人，才会按开关

由于灯的开关按偶数次状态不变，还是关（起始是关），所以，灯的开关只有按奇数次，才会开。

发现问题和上述提到的只有完全平方数有奇数个因子的问题是一样的

也就是如果灯的编号是完全平方数，那么它会被按奇数次，最后就是开着的

输入n轮，所以只需求出<=n的完全平方数就行了。