开关灯问题（质因数分解）
题目描述:
有编号1~n个灯泡，起初所有的灯都是灭的。有n个同学来按灯泡开关，如果灯是亮的，那么按过开关之后，灯会灭掉。如果灯是灭的，按过开关之后灯会亮。
现在开始按开关。
第1个同学，把所有的灯泡开关都按一次(按开关灯的编号： 1,2,3,......)。
第2个同学，隔一个灯按一次(按开关灯的编号： 2,4,6,......)。
第3个同学，隔两个灯按一次(按开关灯的编号： 3,6,9,......)。
......
问题是，在第n个同学按过之后，有多少盏灯是亮着的？
输入描述:
输入一组数据：n输出描述:
输出开着的灯编号样例输入:
10样例输出:
1 2 4 9题意
中文题面，没啥好说的。
题解
- 首先可以想到的一个办法是直接模拟，可以用一个数组来表示开关的状态（0灭1开），然后一层循环遍历表示开关灯泡的次数，一层循环来对灯泡进行操作，时间复杂度$O(n^2)$
- 这题还有有趣的数学解法，来自haolujun。
这个问题有一个数学上的解决方法。可以看出，被按了奇数次的灯泡应该是亮着的，被按了偶数次的灯泡应该是灭的。那么什么样的灯泡被按了奇数次？什么样的灯泡又被按了偶数次呢？从按的过程可以发现，如果一个灯泡的编号具有偶数个因子，那么该灯泡就被按了偶数次，反之按了奇数次。现在的问题又变成，什么样的编号具有奇数个因子，什么样的编号具有偶数个因子？这涉及到一个叫做质因数分解的定理，大概的意思是说，任何正数都能被唯一表示成多个质因数幂次乘积的方式。例如:
14=2*7
50=2*5^2
...
100=2^2*5^2*也就是N=(p[1]^e[1])*(p[2]^e[2])*......*(p[k]^e[k])，其中p[i]是质数，e[i]是p[i]的幂次。而由这个公式我们又可以导出一个数有多少个因子的计算公式:FactorNumber(N)=(e[1]+1)*(e[2]+1)*......*(e[k]+1)。
那么什么条件下满足FactorNumber(N)是奇数呢？显然必须所有的e[1],e[2],......,e[k]都必须是偶数，这样才能保证e[i]+1是奇数，结果乘积才能是奇数。而由于e[1],e[2],......,e[k]都是偶数,那么N一定是一个完全平方数(因为sqrt(N)=(p[1]^(e[1]/2))*(p[2]^(e[2]/2))*......*(p[k]^(e[k]/2))是整数) 。回到按灯泡的问题上来，1~100中完全平方数有1,4,9,16,25,36,49,64,81,100这10个数，也就是说最后只有编号为这10个数的灯是亮着的。
别的没什么好说的，我就说一下为啥FactorNumber(N)=(e[1]+1)*(e[2]+1)*......*(e[k]+1)，比如$50 = 2^1 * 5^2$，然后对于2我们可以选或者不选两种，对于5可以不选或者选一个或者选两个三种，所以FactorNumber(25) = (1+1)*(2+1)，实际上就是组合公式，都不选就是1。
代码
代码就免了吧，可以预处理一下得到某个范围内的完全平方数，然后就直接根据n得结果了。
The end.
2019年3月4日 星期一