319. Bulb Switcher

题目链接 | 我的解答

这道题是智力题。

一开始想到的是暴力算，先把全部 int 个数的灯的亮灯数算出来，再直接查。但是 LeetCode 好像不支持这种模式，对于每个 TestCase 它都会完整的执行整段代码，包括我生成亮灯表的过程。

后来在纸上把前 10 个灯泡的情况列了出来，发现灯是否亮，跟这个数有几个约数有关。偶数个约数的灯不亮，奇数个亮：

 1 => 1
 2 => 1, 2
 3 => 1, 3
 4 => 1, 2, 4
 5 => 1, 5
 6 => 1, 2, 3, 6
 7 => 1, 7
 8 => 1, 2, 4, 8
 9 => 1, 3, 9
10 => 1, 2, 5, 10

这样可能还不够直观，换一种形式：

 1 =>  1x1
 2 =>  1x2
 3 =>  1x3
 4 =>  1x4, 2x2
 5 =>  1x5
 6 =>  1x6, 2x3
 7 =>  1x7
 8 =>  1x8, 2x4
 9 =>  1x9, 3x3
10 => 1x10, 2x5

可以看出约数都是成对出现。但是对于平方数，它有一对约数的乘号两边是相同的数字。这导致它的约数只有奇数个。

所以这个题变成，看 (0, n] 的平方数有多少个。所以一行简单的 (int)sqrt(n) 可以解决。