灯泡开关

所以第 k 盏灯被切换的次数，正好等于 k 的因子个数。

1. 读入：9 盏灯初始全灭。第 i 轮把所有「编号是 i 的倍数」的灯切换一次（亮↔灭）。问 9 轮后还有几盏亮？

2. 第1轮：第 1 轮：1 的倍数是全部，所有灯打开。

3. 第2轮：第 2 轮：编号是 2 的倍数的灯（2,4,6,8）各翻转一次。

4. 第3轮：第 3 轮：编号是 3 的倍数的灯（3,6,9）各翻转一次。

5. 第4轮：第 4 轮：编号是 4 的倍数的灯（4,8）各翻转一次。

6. 第5轮：第 5 轮：编号是 5 的倍数的灯（5）各翻转一次。

7. 第6轮：第 6 轮：编号是 6 的倍数的灯（6）各翻转一次。

8. 第7轮：第 7 轮：编号是 7 的倍数的灯（7）各翻转一次。

9. 第8轮：第 8 轮：编号是 8 的倍数的灯（8）各翻转一次。

10. 第9轮：第 9 轮：编号是 9 的倍数的灯（9）各翻转一次。

11. 结果：9 轮后，只剩 1、4、9 三盏亮着。为什么是它们？看每盏灯被切换了几次——切换偶数次回到灭，奇数次才亮。

12. 为何灯6灭：灯 6 的因子是 1、2、3、6 共 4 个（偶数），被切换偶数次，最后灭。因子总是成对出现（1×6、2×3）。

13. 为何灯9亮：灯 9 的因子是 1、3、9 共 3 个（奇数）。因为 9=3×3，平方根 3 和自己配对、只算一次，所以因子数为奇数，最后亮。

14. 规律：只有完全平方数的因子个数是奇数。所以最后亮的灯，编号都是完全平方数：1=1²、4=2²、9=3²。

15. 返回答案：不超过 n 的完全平方数有 ⌊√n⌋ 个。所以代码一行：return int(√9)=3。无需真的模拟，时间 O(1)。

这题的关键不是模拟，而是把“第几轮会切换”翻译成“编号有哪些因子”。