对于输入的 $N$,$N$ 有多少个约数,第 $N$ 个灯泡就会被更改几次。

由唯一分解定理: $ N = {p_1}^{a_1} \times {p_2}^{a_2} \times \dots \times {p_n}^{a_n} $ 知 $N$ 有 $(a_1 + 1) \times (a_2 + 1) \times \dots \times (a_n + 1) $ 个因数。

欲使第 $N$ 个灯泡最后是开启状态,必须要求因数个数为奇数, 即 $(a_i + 1)$ 都是奇数,即 $a_i$ 都是偶数,即 $N$ 是完全平方数。

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	int n;
	while (cin >> n)
	{
		int root = sqrt(n);
		cout << (root * root == n ? 1 : 0) << endl;
	}
	return 0;
}

文章为 C#.NAME 原创,禁止转载。