题目描述

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

样例

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

算法

(数论) $O(1)$

每个灯泡开关被按的次数等于它的编号的约数个数。
最终灯泡是亮的，说明编号有奇数个约数。

下面我们证明：一个数有奇数个约数，等价于它是平方数。
证明：
首先，对于每个平方数，除了平方根之外，其余所有约数都是成对出现，所以平方数有奇数个约数。
然后，由算数基本定理，一个整数 $n$ 可以唯一表示成：$n = p_1^{k_1} \times p_2^{k_2} \times … \times p_m^{k_m}$。其中 $p_1, … p_m$ 均是质数，$k_1, … k_m$ 均是正整数。
则 $n$ 的约数个数就是 $\prod_{i=1}^m(k_i + 1)$。
如果 $n$ 有奇数个约数，说明 $(k_1 + 1), … (k_m + 1)$ 都是奇数，从而 $k_1, … k_m$ 均是偶数。所以 $n = (p_1^{k_1/2} \times p_2^{k_2/2} \times … \times p_m^{k_m/2})^2$，所以 $n$ 是平方数。

假设共有 $n$ 个灯泡，则从 $1$ 到 $n$ 中共有 $\lfloor \sqrt n \rfloor$ 个平方数。

时间复杂度分析：只需求 $n$ 的平方根，时间复杂度是 $O(1)$。

C++ 代码

class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};