[Math_Medium]319. Bulb Switcher

题目大意

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.

解题思路

题意对于灯的操作：第一次全部点亮，第二次每两个反转一次，第三次，每三个翻转一次.......比如第6个灯泡，只会在第一次点亮，然后第二次灭，然后再在第三次亮，最后在第六次灭，可见每一次操作会是在6的系数上面进行，那么问题转化为到灯泡n有多少个系数，每一个系数意味着反转一次，所以等价于求系数个数的奇偶，每一个数的系数都是成对的，比如1和n,n/q和q等，特殊情况，比如3*3=9，这时只有一个系数。所以对于完全平方数，系数为奇数个，对于非完全平方数，系数有偶数个。
因为初始时灭的，所以若反转奇数次（亮灭亮灭亮....），则最终是亮的
　　　　　　　　　　若反转偶数次（亮灭亮灭....)，则最终是暗的

题目要求这n个灯泡在n次操作后最终还剩下几盏灯亮，通过上面分析，我们可以知道完全平方数有奇数个系数，因此最终会反转奇数次，即最后灯会亮;而对于非完全平方数，其系数会是偶数个，所以最终灯会灭。

因此题目等价于求不小于n的数中有几个是完全平方数，我们可以从1开始算，一直平方，知道这个数的平方大于等于n，即 sqrt(n)

代码如下：

class Solution
{
public:
int bulbSwitch(int n)
　　 　{
　　　　return　sqrt(n);
　　　 }
};

Funny Math