# 319.灯泡开关

#### <https://leetcode-cn.com/problems/bulb-switcher/>

![](/files/NiESLwgzRntMM5ToQUOR)

画出每轮的变化，1表示开灯0表示关灯，由图可知，就是找1\~n有多少个除数，除数为偶数个则最后为0（关灯），为奇数则最后为1（开灯）

统计除数，考虑对称性，如`16=2*8=8*2`，因此当两个因数a、b不相等时一定会存在对称的b、a，相等时只有一对a、b。且遍历找n的除数只需要遍历到到根号n

```python
class Solution:
    def bulbSwitch(self, n: int) -> int:
        res = 0
        for i in range(1, n+1):
            cnt = 0
            j=1
            while j * j <= i:
                if i % j == 0:
                    cnt += 1
                    if j * j != i:
                        cnt += 1
                j += 1
            if cnt % 2:
                res += 1
        return res
```

## 改进

上面方法TLE，其实观察知没必要算n有多少个除数，只需要看n是否为完全平方数（即找到n=j^2）就能判断除数个数是否为奇数

```python
class Solution:
    def bulbSwitch(self, n: int) -> int:
        res = 0
        for i in range(1, n+1):
            j = int(sqrt(i))
            if j ** 2 == i:		#j是i的平方根
                res += 1
        return res
```

依然TLE，继续观察发现，1，2，……，n的完全平方数个数就是floor(根号n)，由于 根号n涉及到浮点数运算，为了保证不出现精度问题，可以计算根号(n+0.5)

```python
class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(sqrt(n + 0.5))
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cai-sen-se.gitbook.io/leetcode/201-400/319.-deng-pao-kai-guan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.