LeetCode Bulb Switcher There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds. Example:

Given n = 3.
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].
So you should return 1, because there is only one bulb is on.

---

给定n盏灯，第一轮是所有灯都是亮的；第二轮每两盏灯触发（亮变灭或灭变亮）一盏灯；第三轮每三盏灯触发一盏灯；如此循环直到第n轮只触发最后一盏灯。问最后有多少盏灯是亮着的。 首先模拟一把： [cpp] class Solution { public: int bulbSwitch(int n) { if (n == 0)return 0; vector<int> bulbs(n + 1, 1); for (int i = 2; i <= n; ++i) { for (int j = 1; j*i <= n; ++j)bulbs[j*i] = !bulbs[j*i]; } int ans = 0; for (int i = 1; i <= n; ++i)if (bulbs[i])++ans; return ans; } }; [/cpp] 本代码提交TLE，过不了大数据集。 然后就把前10的结果列出来了，在OEIS中找到了序列对应的公式：a(n) = floor(sqrt(n))。后来看了网上的题解，得到了这个通项公式的解释： 如果第i盏灯的i的因子有奇数个，则这盏灯最终是亮的，比如9有1,3,9这3个因子，则第9盏灯会分别在第1、3、9轮被触发，由于第1轮是变亮，经过奇数轮之后还是亮的。如果i的因子有偶数个，则类似的分析可知这盏灯最终是灭的。 那么哪些数的因子个数是奇数呢，只有完全平方数的因子个数是奇数，因为非完全平方数的因子都是成对出现的，比如8=1*8=2*4=4*2，而完全平方数有两个因子是重复的9=1*9=3*3，3相当于1个因子。 1~n有floor(sqrt(n))个完全平方数，所以结果就是floor(sqrt(n))。 代码如下： [cpp] class Solution { public: int bulbSwitch(int n) { return floor(sqrt(n)); } }; [/cpp] 本代码提交AC，用时3MS。]]>