滴滴模拟题之开关灯问题

描述

今天晚上做了以下滴滴的模拟题，其中有一道开关灯的问题。题意描述如下，有2015个灯，序号是1~2015，初始都是熄灭的，然后从k=1开始，序号是k的倍数灯拨一下开关，直到k=2015。问：最后亮着的灯有几盏？

讨论

刚看到这道题，在纸上模拟一下了一下几盏灯的情况，并没有发现什么规律。然后就撸代码，先看看答案是多少。

#include <iostream>
#include <vector>
using namespace std;
const int N = 2015 + 1;

int main()
{
	vector<int> num(N, 0);
	for (int i = 1; i < N; ++i)
	{
		for (int j = 1; j < N; ++j)
		{
			if (j%i == 0)
				num[j] = 1 - num[j];
		}
	}
	int count = 0;
	for (int i = 1; i < N; ++i)
	{
		if (num[i] == 1)
		{
			++count;
			printf("√");
		}
		else
			printf("×");
	}

	printf("\nopened lights:%d\n", count);
	system("pause");
}

答案显示是44。总结一下打印中√的规律，发现只有1,4,9,16….，$k^2$位置的灯是亮的。根据这个规律，可以知道 $44^2=1936 <2015<45^5=2025$，那么答案就是44。但是为什么是这样呢？
我们不妨从k=1时开始讨论。
k=1时所有灯全亮，那么当迭代到k=x时，序号为x的灯总共开关了那几次呢？
如果x=6，因数为2，3，那么当k=2时关闭，k=3时又打开，最后k=6时关闭。
如果x=16，因数为2,4,8，没错！多出来的一个4使16位置的灯最终得到打开。
所以我们可以总结出，除1灯外，序号的不包括1和自身的因数为奇数个的灯才能打开，满足条件的这种数恰恰是正整数的平方。