题解 P1876 【开灯】

数学推理~

首先，我们来呱唧一下原理：一开始灯都是关着的，要让它亮起来，则需要扳动开关奇数次。而因数有奇数个的，只有平方数（1、4、9、16……）。

为什么平方数有奇数个因数？

因为一个数，总是由一个乘法算式（两个数相乘）得到的

比如 36=4×9,7=1×7,120=12×10等等。

所以，非平方数的数总是有偶数个因数。

但平方数有一组算式是由两个相同的数乘起来的，只能算一个数。

例如36，它等于

1×36

2×18

3×12

4×9

6×6

OK,共五组，2×5-1=9个因数。（偶-奇=奇）

辣么，上代码！

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=sqrt(n);i++) cout<<i*i<<" ";
	return 0;
}

byebye~