1. 题目描述

最开始有n个灯泡，编号从1到n，都是灭的。
第一次打开所有灯泡；
第二次按下编号是偶数的灯泡开关（亮的变灭，灭的变亮）；
第三次按下编号是3的倍数的灯泡开关；
…
第n次按下最后一个灯泡的开关。
请问最终有多少个灯泡是亮的。

2. 样例

输入：3
输出：1
解释：
最开始三个灯泡的状态是 [灭，灭，灭]；
第一次按开关以后变成：[亮，亮，亮]；
第二次按开关以后变成：[亮，灭，亮]；
第三次按开关以后变成：[亮，灭，灭]；

3. 分析

问题转化为求1~n有多少个数字的约数个数为奇数个。

3.1 解法一

联想到提高课中“轻拍牛头”那道题，可以反着求每个数的约数个数。对于1~n中的某一个数i，枚举它的所有倍数，计算他对它的倍数约数个数的贡献。

时间复杂度分析

$$ (n / 1) + (n / 2) + (n / 3) + … + (n / n) = nlogn $$

代码

class Solution:
    def bulbSwitch(self, n: int) -> int:
        h = [0 for i in range(n + 1)]
        for i in range(1, n + 1):
            j = 1
            while i * j <= n:
                h[i * j] += 1
                j += 1
        res = 0
        for i in range(1, n + 1):
            if h[i] % 2 == 1:
                res += 1
        return res;

3.2 解法二

有这样的结论：一个数字的约数个数是奇数个等价于这个数字是完全平方数

证明必要性

如果n是完全平方数，那么除了$\sqrt(n) \times \sqrt(n)$，其余的约数对均包含两个数字，因此完全平方数有奇数个约数。

证明充分性

约数个数的问题常常会和质因子分解结合在一起,设：
$$ n = p_1^{a_1}\times p_2^{a_2}\times … \times p_k^{a_k} $$
因此约数个数为$(a_1 + 1)\times … \times (a_k + 1)$,又因为约数个数为奇数个，因此$a_1…a_k$都必须是偶数，所以n可以写作：
$$ n = (p_1^{\frac{a_1}{2}}\times p_2^{\frac{a_2}{2}}\times … \times p_k^{\frac{a_k}{2}})^2 $$
因此n是完全平方数。

证明了这个结论之后原问题就等价于1~n中有多少个完全平方数，代码为：

class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(sqrt(n))