Leetcode 319 - Bulb Switcher（Math）

题意

点灯问题，有n个灯，进行n轮操作：

第i轮，将i的所有整数倍灯的状态翻转，比如第2轮，将2,4,6…的灯的状态翻转。

初始状态是所有灯都是熄灭的。

求最后亮着的灯的个数。

思路

首先，对于每个灯i，我们只需要确定它被翻转的次数x的奇偶性即可。

当x为奇数时，最后i是亮着的。

当x为偶数时，最后i是熄灭的。

那么我们确定x的奇偶性。

我们需要明确的是，当灯i在第k轮被翻转的情况下，有i%k=0$i /% k = 0$，即k是i的因子。

所以，问题就转化成了求i的因子个数的奇偶性。

然后，解决其奇偶性问题的关键是：在一般情况下，因子是成对出现的。

比如：i=24$i = 24$，那么有i=1⋅24=2⋅12=3⋅8...$i = 1/cdot 24 = 2/cdot 12 = 3/cdot8...$

即在一般情况下，有i=p⋅qp<q$i = p /cdot q /quad p < q$，即因子个数成对出现。

然后需要确定的就是因子个数单独出现的情况，很显然即i=p⋅qp=q$i = p /cdot q /quad p = q$。此时i的因子个数是奇数。即i是完全平方数。

最后，我们的点灯问题的解就转化成了：求小于等于n范围内完全平方数的个数。显然结果为n√$/sqrt n$。

代码