319. 灯泡开关

题目

初始时有 n 个灯泡处于关闭状态。
对某个灯泡切换开关意味着：如果灯泡状态为关闭，那该灯泡就会被开启；而灯泡状态为开启，那该灯泡就会被关闭。
第 1 轮，每个灯泡切换一次开关。即，打开所有的灯泡。
第 2 轮，每两个灯泡切换一次开关。 即，每两个灯泡关闭一个。
第 3 轮，每三个灯泡切换一次开关。
第 i 轮，每 i 个灯泡切换一次开关。 而第 n 轮，你只切换最后一个灯泡的开关。
找出 n 轮后有多少个亮着的灯泡。

示例 1：

319. 灯泡开关 - 图1

  1. 输入：n = 3
  2. 输出：1 
  3. 解释：
  4. 初始时, 灯泡状态 [关闭, 关闭, 关闭].
  5. 第一轮后, 灯泡状态 [开启, 开启, 开启].
  6. 第二轮后, 灯泡状态 [开启, 关闭, 开启].
  7. 第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 
  9. 你应该返回 1，因为只有一个灯泡还亮着。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：1

提示：

  • 0 <= n <= 10^9

题解

首先思考对于第 i 个灯泡，其状态转变了多少次？
答案是 i 的因子的个数。
但是我们不需要算出有多少个，我们很容易发现，一般的数的因子的个数都是偶数个。
因为若 a 是 n 的因子，即 n%a==0，那么也相应的有 n%(n/a)==0。
每个因子 a 会有另一个对应的因子 n/a，因此一般的因子数都是偶数个。
但是也会有这两个因子相等的情况，也就是n为完全平方数，此时n的因子数为奇数个。
灯泡进行偶数次状态变换之后，还是熄灭的，所以如果第 i 个灯泡最后还亮着，说明 i 是完全平方数。
最后只需求出1~n中有多少完全平方数即可。

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