灯泡开关算法题：从暴力模拟到完全平方数的O(1)解法

这道题我印象深刻。上个月帮人模拟笔试，一道"灯泡开关"，对面哥们看完题目嘴角扬起，心想这是什么送分题，直接两层循环模拟翻转。结果看到参数范围那个瞬间，笑容凝固了——n是十的九次方量级。我当场就笑了，这道题名字起得真客气，看着是人畜无害的模拟，实际是来收编"只会写模拟的人"的。

"灯泡开关"是一道非常典型的笔试筛选器，它想考察的不是你会不会写循环，而是你有没有意识到：有些问题表面上在考编码，实际上在考数学直觉。这道题在LeetCode上是319题，在各大厂笔试里也反复出现，披着模拟的外衣考数论。今天这篇就把它的来龙去脉掰开揉碎讲清楚，看完你不仅在笔试里能秒杀这题，还能顺手看懂它的一整串变形题。

1. 一道看起来能暴力，实际想让你放弃暴力的题

1.1 题目在说什么：以n=10手算一次

先把题目定个型。假设有n个灯泡，编号从1到n，初始全部关闭。接下来进行n轮操作：第i轮，翻转所有编号为i的倍数的灯泡。翻转的意思就是，开着变关，关着变开。问你第n轮操作结束后，有多少个灯泡是亮着的。

听起来很简单对吧？我习惯遇到这种题先手算一个小规模样例，比如n=10，把每一轮的翻转结果列出来，这样比空想直观得多。

n=10的时候，结果是3个灯泡亮着，亮灯编号是1、4、9。到这一步，规律其实已经呼之欲出了——亮着的灯泡编号全是完全平方数：1=1²，4=2²，9=3²。

但注意，这只是n=10的观察结果，还不能当作定论。做笔试题最忌讳的就是"看到三个点就总结规律"，你得先明白这规律是怎么来的，才能确定它在大数据范围下依然成立。

1.2 为什么说这道题"阴"

如果说"最终规律是平方数"是终点，那这道题的恶意就藏在起点。如果n给的是10⁹，你老老实实写个模拟，外层循环跑n次，内层循环平均也得跑n/2次，总操作量是十万亿级别，跑完怕是笔试都结束了。

所以这道题真正想干的事，是逼你停下来想：灯泡的翻转次数，到底取决于什么？一旦开始想这个问题，你就会被引导到"约数个数"的方向上。这也是为什么我反复强调，笔试里遇到"看起来能做但数据范围非常离谱"的题，第一反应不应该是优化循环，而是重新审视问题本身。

2. 暴力模拟法：写得出来，不一定跑得完

2.1 朴素的翻转实现

不管怎么说，暴力模拟是理解这道题的第一步。代码写起来很直接：用一个布尔数组记录灯泡状态，第i轮把所有下标为i的倍数的元素取反。

int bulbSwitch(int n) { vector<char> bulbs(n + 1, 0); // 0表示灭，1表示亮 for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j += i) { bulbs[j] ^= 1; } } int ans = 0; for (int i = 1; i <= n; i++) { if (bulbs[i]) ans++; } return ans; }

这里我用vector<char>而不是vector<bool>，因为vector<bool>在C++里是个特化容器，内部按位存储，虽然省内存，但行为有时不符合常规预期，面试笔试中没必要踩这个坑。内层循环的起始位置是j = i而不是j = 1，理由很简单：编号小于i的灯泡不可能是i的倍数，从i开始遍历能省掉一半无意义的判断。

这个实现的正确性毋庸置疑，但它到底有多慢？你计算一下总的翻转次数：第1轮翻转n次，第2轮翻转n/2次，第3轮翻转n/3次……总次数是：

n/1 + n/2 + n/3 + ... + n/n = n * (1 + 1/2 + 1/3 + ... + 1/n)

括号里的调和级数收敛速度很慢，近似等于ln(n)再加上欧拉常数γ（约0.577）。所以总的操作量大约是n ln n。

2.2 暴力与公式的分水岭在哪里

用具体数字感受一下：

笔试里这题敢把n开到10⁹，就是在明明白白告诉你：别模拟了，去寻找O(1)的解法。但暴力代码也不是白写的，它最大的价值在于：当你在笔试现场拿不准公式的时候，可以用暴力跑n=100以内的数据来验证你的猜想。这是后话，后面我会专门讲这个技巧。

3. 破题的关键一步：翻转次数就是约数个数

3.1 把"轮次"翻译成"整除关系"

现在来干正事。我们单独盯着某一个灯泡，比如编号为k的灯泡，它什么时候会被翻转？

第i轮会翻转所有编号为i的倍数的灯泡，也就是说，灯泡k在第i轮被翻转，当且仅当"k是i的倍数"，换个说法就是"i能整除k"。这句话反过来读更顺：k的每一个约数i，都会对应一次翻转。

所以结论很简单也很关键：灯泡k在整个过程中的翻转次数，恰好等于k的正约数个数。数论里通常记作d(k)或τ(k)。

为什么说这个转化是破题点？因为原本的问题是"二维的"：你有n个轮次，n个灯泡，看起来像一张n×n的表格。但换个角度后，每个灯泡的状态只取决于它自己的一个一维属性——约数个数。维度直接降下来了，复杂度分析的目标也从"模拟所有轮次"变成了"分析约数个数的性质"。

3.2 约数的"成对出现"与唯一的落单者

有了"翻转次数 = 约数个数"这个翻译，题目就变成了：哪些数k，它的约数个数是奇数？

初始状态灯泡是灭的，翻转一次变亮，翻转两次变灭，翻转三次变亮……所以翻转奇数次，最终就是亮的。问题进一步收敛为：什么样的数有奇数个约数？

答案藏在约数的配对规律里。随便取一个数，比如12，它的约数是1、2、3、4、6、12。你会发现这些约数可以两两配对：(1, 12)、(2, 6)、(3, 4)，每一对的乘积都是12。只要d不等于k/d，约数d就总能找到另一个约数和它配对，成对出现的约数贡献了偶数个名额。

那什么时候配对会失败？当d = k/d的时候，也就是k = d²的时候。这个时候d和自己配了对，这个"落单的"约数不会被消耗掉，约数个数就比偶数多了一个变奇数。

我到这一步通常会给学生打个比方：约数配对就像舞会入场券，每个约数都该找个人组队，但完全平方数的中间那个约数比较特殊，它只能自己抱着自己跳，于是队伍数量多了个单数。这个单数的一支队伍，决定了灯泡最终是亮的。

4. 为什么只有完全平方数是特例：数论视角补一刀

4.1 用标准分解式看约数个数的奇偶性

"约数成对出现"这个解释已经很直观了，但笔试里万一遇到追问，面试官可能会想听更严谨的数论表达。这里补一刀：整数k可以写成标准分解式：

k = p1^a1 * p2^a2 * p3^a3 * ... * pm^am

其中p1、p2……是互不相同的质数，a1、a2……是对应的指数。约数个数的计算公式是：

d(k) = (a1 + 1) * (a2 + 1) * (a3 + 1) * ... * (am + 1)

这个公式的来历不复杂：k的任意一个约数，它的每个质因子的指数只能从0到ai之间取，所以每个质因子有ai+1种选择，乘法原理相乘即可。

现在要让d(k)是奇数。奇数乘以奇数才是奇数，只要任何一个因子是偶数，乘积就是偶数。所以每个括号(ai + 1)都必须是奇数。这意味着每个ai都必须是偶数。每个指数都是偶数，这样的数是什么？正是完全平方数。

这个角度实际上给前面的"配对论"提供了代数证明，也能让你在面试时显得更专业。但如果你觉得记公式麻烦，"成对配对"那个思路已经完全够用了，笔试不是写论文，能自圆其说就行。

4.2 答案公式：亮着的灯编号是一串平方数

把前面的结论串起来：

• 灯泡k翻转次数 = 约数个数d(k)
• d(k)为奇数当且仅当k是完全平方数
• 初始熄灭，翻转奇数次后点亮

所以最终亮着的灯泡，其编号一定是1²、2²、3²……这些完全平方数中不超过n的那些。答案是这些编号的个数，也就是满足i²≤n的最大整数i，即⌊√n⌋。

用数学语言写就是：

ans = floor(sqrt(n))

回到n=10的例子，⌊√10⌋ = 3，亮灯编号是1、4、9，完全吻合之前手算的结果。到这儿，题目从一个n×n的模拟问题，变成了一行求平方根的问题，复杂度从O(n log n)直接降到了O(1)或者O(log n)。

5. 五个语言写完这题的O(1)解法，以及防精度坑

5.1 各语言实现对照表

公式已经出来了，代码就没什么技术含量了。关键是各语言在求整数平方根时的微小差异，容易在笔试环境里出问题。

C++：

#include <cmath> class Solution { public: int bulbSwitch(int n) { return (int)sqrt(n); } };

Java：

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

Python：

import math class Solution: def bulbSwitch(self, n: int) -> int: return math.isqrt(n)

Go：

import "math" func bulbSwitch(n int) int { return int(math.Sqrt(float64(n))) }

JavaScript：

var bulbSwitch = function(n) { return Math.floor(Math.sqrt(n)); };

5.2 浮点开方可能踩的坑与二分替代法

上面这些写法里，C++、Java、Go、JavaScript走的都是浮点开方再转整型的路子。大多数情况下没问题，但做笔试的人应该养成一个习惯：凡是涉及浮点转整数，都要问自己一句"精度够不够稳"。

浮点开方的风险在于：某些完全平方数，比如25，开方后理论结果是5.0，但浮点运算底层算出来的可能是4.999999999999，取整就成4了。这种问题在数据量大的时候不是会不会发生，而是什么时候发生。

我个人的处理习惯是加一个回验，花不了几行代码，但能把精度坑彻底填平：

int bulbSwitch(int n) { int q = (int)sqrt(n); // 如果下一位的平方也不超过n，说明浮点结果偏小了 if ((long long)(q + 1) * (q + 1) <= n) q++; return q; }

注意这里转long long的原因：当q接近46340的时候，q²会逼近int类型的上限2.1×10⁹，直接乘会溢出。笔试环境里这种隐蔽的溢出错，比算法想不出来还要冤。

如果你对浮点完全不放心，还可以用整数二分来求平方根，复杂度O(log n)，对n=10⁹来说也就三十次循环，完全可以在毫秒级跑完：

int bulbSwitch(int n) { long long l = 0, r = n, ans = 0; while (l <= r) { long long mid = l + (r - l) / 2; if (mid * mid <= n) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return (int)ans; }

二分法的优势是不依赖浮点环境，纯整数运算没有精度问题，笔试时如果时间紧张、不敢赌sqrt的精度，直接上这个版本最省心。Python的话就没这些纠结，math.isqrt内部就是纯整数的平方根算法，专门为这种场景设计的，性能好而且绝对精确。

5.3 用暴力脚本验证公式

写代码最怕的就是"公式背错了但是自己不知道"。我有一套固定的验证方法：写一个暴力版本，再写一个公式版本，然后在小范围内对拍。保证公式正确性的同时，也能加深自己对题目的理解。

import math def brute(n): bulbs = [False] * (n + 1) for i in range(1, n + 1): for j in range(i, n + 1, i): bulbs[j] = not bulbs[j] return sum(bulbs) def fast(n): return math.isqrt(n) for n in range(1, 1000): if brute(n) != fast(n): print("mismatch at", n) break else: print("all ok")

这段脚本我在笔试复习时跑过很多次，输出"all ok"的那一刻，你对这个公式的信心会变得非常足。这个"暴力+公式对拍"的习惯，不只是这道题适用，几乎所有需要找规律的笔试题都能用。笔试环境如果允许本地写代码，这就是你的私人纠错器。

6. 笔试现场才需要懂的延申：这题的亲戚们

6.1 变体一：输出亮灯编号而不是数量

有些笔试不会问"亮灯有多少个"，而是让你"列出所有亮着的灯泡编号"。这个更简单，因为亮灯编号就是1²、2²、3²……一直乘到超过n为止：

vector<long long> getOnBulbs(int n) { vector<long long> ans; for (long long i = 1; i * i <= n; i++) { ans.push_back(i * i); } return ans; }

注意循环变量用long long，因为i*i在i达到46341时就会超出int范围。这个变体的考点其实已经从数学转向了"你有没有处理溢出"的意识。

6.2 变体二：名字相同、解法不同的"灯泡开关II"

LeetCode上还有一道题叫"灯泡开关II"，名字看起来和这道题是双胞胎，实际上完全是另一路货色。那道题里有四个功能不同的开关按钮，可以按m次，问最后能得到多少种不同的灯泡状态组合。解法和约数没关系，需要分析按钮操作之间的等价关系，用状态压缩枚举可能的状态。笔试时如果看到"灯泡开关"后面带罗马数字，建议先别急着套平方数结论，把题目完整读一遍再说。

这种"同名不同解"的题目，其实也是出题人故意埋的坑：想考你有没有认真审题。我见过不止一个人看到"灯泡"两个字就开始写sqrt，结果整道题跑偏。

6.3 变体三：关灯游戏与异或方程组

还有一个相关的经典问题叫"Lights Out"，中文常翻译成关灯游戏或灭灯游戏。面板是一个m×n的格子矩阵，点一个格子会翻转自己和上下左右五个格子的状态，要求把所有灯熄灭。这类问题的思路和这道题完全不同，不再考约数，而是考线性代数里的异或消元，每个格子的点击次数要么是0要么是1，最后列一个异或方程组解出来即可。

把这个亲戚列出来是想说明一个道理：灯泡开关这系列的题目核心都在"翻转奇偶性"上，落点却各不相同。有的落在约数、有的落在状态组合、有的落在方程组。笔试准备时背结论不如练思维，遇到翻转类题目先想清楚"这个翻转受什么影响、影响能不能用数学结构表达"，就成功了一大半。

笔试策略上，我自己总结了一条实战经验：看到n的取值范围大到离谱，同时题面上出现倍数、整除、约数、轮次这类词汇，先别着急开循环，停下来手算几个小样例，观察输出序列的规律，再回头想为什么。这个习惯在"灯泡开关"上帮我省了至少十分钟，那十分钟足够把整张卷子的其他题目再检查一遍。

如果你在考场上实在推不出公式，也有一个保底策略：先提交一版暴力解，保证小数据范围内的分数到手，再利用剩余时间思考优化。很多OJ是按数据范围分档给分的，暴力能拿一部分分，公式解能拿满分，别让"完美主义"害得你连保底分都没拿到。

灯泡开关这道题，表面考的是灯泡和开关，实际考的是你敢不敢在"能写"和"能过"之间选择后者。刷题刷多了你会发现，真正拉开差距的往往不是coding的熟练度，而是遇到反常数据范围时那种"停下来想"的定力。希望这篇把规律讲透、把坑填平的再读版，能让你下次在笔试里遇见它时，多一分从容少一分慌张。