P1876 开灯【入门】
开灯
题目描述
首先所有的灯都是关的（注意是关！），编号为 1 1 1 的人走过来，把是 1 1 1 的倍数的灯全部打开，编号为 2 2 2 的人把是 2 2 2 的倍数的灯全部关上，编号为 3 3 3 的人又把是 3 3 3 的倍数的灯开的关上，关的开起来……直到第 N N N 个人为止。
给定 N N N，求 N N N 轮之后，还有哪几盏是开着的。
输入格式
一个数 N N N，表示灯的个数和操作的轮数。
输出格式
若干数，表示开着的电灯编号。
样例 #1
样例输入 #1
5
样例输出 #1
1 4
提示
对于 100 % 100 \% 100% 的数据， 1 ≤ N ≤ 2 40 1 \le N \le 2^{40} 1≤N≤240。
思路：（其实巨简单）
因为一开始的灯是关的，如果最后想让灯是开着的情况，那么这个灯的开关就要按奇数次，而如果开关被按了偶数次，那最后还是关着的。
每次开关灯都和倍数有关，如果这个灯的序号是完全平方数，那么它就会被按奇数次，那么最后也就是开的状态；如果序号不是完全平方数，则会被按偶数次，因为当一个数不是完全平方数时，那么它的因子是偶数个，只要有一个数是它的因子，那么用 这个数 除 当前因子 所得即为该数的另一个因子。
奉上代码（比头文件还短）
#include<iostream>#include<vector>#include<string>#include<sstream>#include<queue>#include<stack>#include<cmath>#include<algorithm>#include<cstring>using namespace std;int a[10001]={0};int main(){int n;cin>>n;for(int i=1;i*i<=n;++i)cout<<i*i<<" ";return 0;}
其他dalao的思路：（引用一下）
看了看别人的题解，都是枚举小于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的完全平方数就行了。
约定不等于承诺〃
怼烎@
野性酷女
还没有评论，来说两句吧...