P1876 开灯
题目背景
该题的题目是不是感到很眼熟呢?
事实上，如果你懂的方法，该题的代码简直不能再短。
但是如果你不懂得呢？那。。。（自己去想）
题目描述
首先所有的灯都是关的（注意是关！），编号为1的人走过来，把是一的倍数的灯全部打开，编号为二的的把是二的倍数的灯全部关上，编号为3的人又把是三的倍数的灯开的关上，关的开起来……直到第N个人为止。
给定N，求N轮之后，还有哪几盏是开着的。
输入输出格式
输入格式：
一个数N
输出格式：
若干数，表示开着的电灯编号
输入输出样例
输入样例#1：
5
输出样例#1：
1 4
说明
1<=N<=2^40
数学题！
#include<cstdio>
#include<cmath>
long long n;
int main()
{
scanf("%lld",&n);
long long a=sqrt((double)n);
for(int i=1;i<=a;i++){
printf("%lld ",i*i);
}
}
从现在开始再也不水水题了
这将是水库里最后一道水题
想到之后很显然，操作k次灯是关着的，操作k+1次灯是开着的。被操作的次数取决于灯编号的因数个数，只有满足存在p使n=p^2，编号n才有奇数个公因数。
可以用反证法证明。
假设一个正整数n,使n满足n=p*p,p∈Z且p有偶数个因数。则另有一正整数q满足n=q*q，则n的算术平方根为p和q，而正整数的算术平方根只有一个，二者矛盾。