问题描述：【Math】319. Bulb Switcher
解题思路：
灯泡开关。初始时有 n 个灯泡关闭，第 i 轮，每 i 个灯泡切换一次开关。找出 n 轮后有多少个亮着的灯泡。
刚开始写了个暴力版 O(n^2)，但是超时了，代码如下：
class Solution:
def bulbSwitch(self, n: int) -> int:
bulbs = [0] * n
i = 1
while i <= n: # 第i轮
for j in range(i-1, n, i): # 每i个灯泡切换一次开关
bulbs[j] = 1 - bulbs[j]
i += 1
return sum(bulbs)
但是，很明显这道题是有规律可循的。可以发现，对于编号为 x 的灯，它切换的次数就是 x 的因数的个数。比如编号为 8 的灯，会在 1、2、4、8 时被切换。如果切换次数（因子个数）为偶数，最后肯定是关；如果切换次数（因子个数）为奇数，最后肯定是开。因此这道题转化为求解因子个数为奇数的灯有几个。
如果我们从 1 一个个去求到 N，计算每个数的因子个数，那样时间复杂度也近似于 O(n^2)，所以也不对。注意到：除了完全平方数外，其他所有数的因子都是偶数个（包括质数）。而完全平方数的因子个数为奇数个（比如 36 的因子为 1、2、3、6、12、18、36，总共 7 个），因此我们只需要统计 n 以下的完全平方数个数即可。时间复杂度为 O(1)。
Python3 实现：
class Solution:
def bulbSwitch(self, n: int) -> int:
return int(n ** 0.5) # 计算n以下的完全平方数有多少个
问题描述：【Math】672. Bulb Switcher II
解题思路：
灯泡开关 2 。有 n 只已经打开的灯泡和 4 个按钮，每个按钮有不同的切换灯泡的功能。在进行 m 次未知操作后，返回这 n 只灯泡可能有多少种不同的状态。
- 考虑 n = 3 的情况：m = 1 时，有 4 个状态；m = 2 时，有 7 个状态；m >= 3 时，有 8 个状态；
- 考虑 n = 4 的情况：m = 1 时，有 4 个状态；m = 2 时，有 7 个状态；m >= 3 时，有 8 个状态；
因此，我们猜想，对于 n >= 3，会不会都是上面这样的答案？答案是 YES。虽然感觉是找规律，但是我也不会证明。
而对于 n = 1 和 n = 2 的情况，我们单独考虑即可。
鉴于这道题被踩的那么惨，实际上也没有做的必要了，参考代码如下。
Python3 实现：
class Solution:
def flipLights(self, n: int, m: int) -> int:
if m == 0: return 1
if n == 1: return 2
if n == 2 and m == 1: return 3
if n == 2 and m > 1: return 4
if m == 1: return 4
if m == 2: return 7
if m > 2: return 8
