开关灯泡靠模拟？不懂这个规律，你写的代码永远是O(n²)

“开关灯泡靠模拟？不懂这个规律，你写的代码永远是O(n²)”

你是不是也写过这样的代码：
一轮一轮去翻灯泡，直到第 n 轮结束？
结果 n=10 万的时候，程序直接“人间蒸发”。

更扎心的是——
这个题，其实根本不需要模拟。

👉很多人卡在代码，其实是卡在认知。

一、引子：你以为是模拟题，其实是数学题

“灯泡开关（Bulb Switcher）”这个题，看起来特别直观：

• 有 n 个灯泡，初始全关
• 第1轮：全部打开
• 第2轮：每2个翻转一次
• 第3轮：每3个翻转一次
• ……

问：最后有多少灯是亮的？

大多数人的第一反应是：

👉 模拟！

但很遗憾，这条路从一开始就是错的。

二、本质拆解：谁会被翻转奇数次？

我们换个角度：

👉 每个灯泡被翻转多少次？

比如第 k 个灯泡：

它会在这些轮被操作：

• 第1轮（1是它的因子）
• 第k轮（k是它的因子）
• 所有能整除 k 的数

也就是说：

👉第 k 个灯泡，被翻转的次数 = k 的因子个数