企业官网建设流程全解析

1. 灯泡开关这道题，到底在考什么

1.1 先把题目翻译成人话

题目原文通常长这样：房间里有 n 盏灯，初始全部熄灭。第 1 轮按下所有灯的开关，第 2 轮按下编号为 2 的倍数的开关，第 3 轮按下编号为 3 的倍数的开关……第 i 轮按下编号为 i 的倍数的开关。问经过 n 轮之后，还有几盏灯亮着？

我带着学弟学妹刷题时，要求他们做的第一件事永远是"把题目翻译成人话"。每一轮按压只会影响一批灯，而具体到某一盏灯，比如编号 12 的灯，它只在轮次为 12 的约数时会被碰到：第 1、2、3、4、6、12 轮，总共被按 6 次。按一次改变一次状态，按偶数次就回到熄灭，按奇数次才会停在点亮。

这个翻译思路很关键，它把"逐轮模拟"变成了"逐灯分析"。很多人一上来就写双层循环模拟，开个布尔数组，外层循环 i 从 1 到 n，内层循环 j 从 i 到 n 步进 i，遇到就取反。逻辑完全没问题，但笔试中这题通常放在限时 10 到 15 分钟的编程题位置，n 一大就露怯。纯模拟的复杂度是 O(n log n)，n 取 10 的 9 次方直接爆炸，所以我常说这题第一关考的其实是"你有没有停下来思考的习惯"。

1.2 为什么笔试这么爱出这道题

我这两年和不少大厂的朋友交流过题库，灯泡开关几乎出现在所有主流公司的算法笔试题库里。原因很简单：它的表面是一个模拟题，底层却是一个数论题，区分度极高。只会写循环的人能拿基础分，能看出约数规律的人才能拿满分，一道题就把"刷题型选手"和"思考型选手"分开了。

它还顺手考察了三个基本功：枚举约数的能力、观察数据规律的能力、以及把数学结论翻译成代码的能力。这三个能力恰好是笔试的高频考点，出题人当然喜欢。更重要的是，题目本身没有复杂的场景包装，不需要解析题意，不涉及任何数据结构，任何一个候选人拿到题都能立刻开始思考，这保证了笔试的公平性，也保证了区分度不受背景知识干扰。

所以不要小看这道"简单题"。我见过不少简历写满项目的人在这道题上翻车，也见过刚入门三个月的新人用十几分钟给出完美解。它考的不是知识储备，而是你在压力下愿不愿意做一步"多想想"。

2. 核心规律：灯亮不亮，取决于约数个数的奇偶

2.1 一盏灯的最终状态如何确定

把视角从"轮次"切换到"单盏灯"之后，问题就变得非常干净。一盏编号为 k 的灯，在 n 轮操作过程中会被按到的次数，恰好等于 k 在 1 到 n 范围内的约数个数。因为第 i 轮会按到编号为 i 的倍数的灯，也就是说当 i 整除 k 时，灯 k 会被按一次。把所有能整除 k 的 i 都数一遍，就是这个灯被按的总次数。

状态翻转的规律是：初始熄灭，按 1 次亮，按 2 次灭，按 3 次亮。所以最终亮着的条件是"按了奇数次"。到这里，原题"n 轮之后有几盏灯亮"就被等价转化成了另一个问题：在 1 到 n 之间，有多少个数的约数个数是奇数？

这个转化是整个题目的灵魂。我教过的人里，有相当一部分能走到这一步，但卡在"怎么数约数个数为奇数的数"上。这里不需要一个一个去试除，而是要想到约数都是成对出现的。

2.2 约数成对出现，唯独平方数例外

随便拿一个数，比如 18，它的约数是 1、2、3、6、9、18。你把它两两配对：1 和 18，2 和 9，3 和 6。每一对相乘都等于 18 本身，所以约数总数一定是偶数。这个规律对几乎所有正整数都成立。

但有一种特殊情况：当这个数是一个完全平方数，比如 16，它的约数是 1、2、4、8、16。配对看看：1 和 16，2 和 8，剩下 4 和 4——自己和自己配对了。理论上这一对只能算一个约数，所以约数总数变成了奇数。换句话说，一个正整数的约数个数为奇数，当且仅当它是完全平方数。

这就是整道题的突破口。亮着的灯编号，必然对应 1 到 n 之间的完全平方数。回到刚才的例子，编号 12 有 6 个约数，6 是偶数，所以灯 12 最终熄灭；编号 16 有 5 个约数，5 是奇数，所以灯 16 最终点亮。亲手验算一遍之后，你会发现这个规律稳如老狗。

2.3 从物理操作到数学结论的完整链条

我习惯把这类题的思考链条写在纸上，方便复盘：初始全灭，这是状态 0；每一轮按到的灯，编号必须是轮次的倍数；第 i 轮的影响范围是 {i, 2i, 3i, ...}；所以灯 k 被影响的轮次集合是 k 的所有约数；被按次数 = 约数个数；约数个数为奇数 ⇔ k 为完全平方数；所以最终亮着的灯是 1^2, 2^2, 3^2, ..., floor(sqrt(n))^2；答案就是 floor(sqrt(n))。

这个链条每一步都简单，但串起来需要一点数学直觉。笔试现场没有人会给你提示，所以平时训练时要养成"把操作性问题往数学性质上靠"的习惯。遇到"被某些操作反复作用"的题，先想每个对象被作用的次数，再想次数的奇偶性，往往比直接模拟靠谱得多。

3. 三种解法的演进，见证一个优化思路的诞生

3.1 暴力模拟：能过小数据，别挑战大数据

第一版解法适合用来验证理解，也适合在笔试小数据用例中拿保底分。直接开一个长度为 n + 1 的布尔数组，true 表示亮，false 表示灭，初始全 false。外层循环 i 从 1 到 n，内层循环 j 从 i 到 n，步长为 i，每次执行bulbs[j] = !bulbs[j]。最后遍历数组统计 true 的数量。

int bulbSwitchSimulation(int n) { vector<bool> bulbs(n + 1, false); for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j += i) { bulbs[j] = !bulbs[j]; } } int count = 0; for (int i = 1; i <= n; i++) { if (bulbs[i]) count++; } return count; }

这个写法的时间复杂度是 O(n log n)，因为内层循环总次数是 n/1 + n/2 + ... + n/n，约等于 n log n。空间复杂度 O(n)。n 在 1000 以内跑起来毫无压力，但 n 到 10^5 就开始卡顿，n 到 10^6 在笔试环境里基本就是超时预定。它的价值在于：给你一个可信的基准答案，后续任何优化版本都可以拿它来对拍验证。

3.2 枚举约数计数：避开模拟，但依然不够快

第二版解法不再模拟整个过程，而是直接对每盏灯数约数个数。枚举 i 从 1 到 n，对于每个 i，用试除法统计约数个数，判断是否为奇数。时间复杂度 O(n sqrt n)，空间复杂度 O(1)。这个版本比模拟聪明，因为不需要开数组，但依然无法应对大数据。

def bulb_switch_divisor(n): ans = 0 for k in range(1, n + 1): cnt = 0 d = 1 while d * d <= k: if k % d == 0: cnt += 1 if d * d != k: cnt += 1 d += 1 if cnt % 2 == 1: ans += 1 return ans

这个版本最大的意义，是让你从"模拟过程"走到"分析性质"这一步。走到这一步，你其实已经摸到答案的边了，差的就是把"完全平方数"这个结论点破。我实际带人的经验是，让候选人先写出这个版本，再去问他"哪些数的约数个数是奇数"，大部分人想几分钟就能给出平方数的答案。这个递进过程，比直接背结论有意义得多。

3.3 数学解法：一行代码的事

最终结论已经很清楚：1 到 n 范围内完全平方数的个数是 floor(sqrt(n))。因为完全平方数是 1^2、2^2、3^2……最大到 m^2 不超过 n，所以 m = floor(sqrt(n))。代码只需要一行。

import math def bulb_switch(n): return int(math.isqrt(n))

Python 3.8 以后建议直接用math.isqrt，它专门返回整数平方根，避免浮点数精度问题。C++ 里可以用(int)sqrt(n)，但后面我会专门讲这里的坑。Java 同样用(int)Math.sqrt(n)，配合原地取整即可。

int bulbSwitch(int n) { return (int)sqrt(n); }

一行代码，时间复杂度 O(1)，空间复杂度 O(1)。从 O(n log n) 到 O(n sqrt n) 再到 O(1)，这三级跳把算法优化的核心理念展示得淋漓尽致：先正确，再高效，最后优雅。笔试时如果你能直接给出这个版本，并且把推导过程写得清清楚楚，这道题基本就是满分。

3.4 三种解法的复杂度对比速查

我建议所有准备笔试的人都把这张表记在脑子里，不是为了应付这题，而是为了建立一种条件反射：看到"多个操作反复施加"的题目，先想有没有数学规律，想不出来再回头暴力。暴力不是可耻的，只暴力不复盘才是。

4. 笔试场上的高频变体，一个比一个阴

4.1 变体一：只问到第 k 轮的状态

原题是问 n 轮之后，但很多笔试喜欢改成：只执行前 k 轮（k 可能小于 n），问此时有多少盏灯亮着。这个变体让很多背答案的人当场懵住，因为他们只记住了"答案是 sqrt(n)"，不知道这个结论从哪里来，更不知道怎么推广。

分析思路其实一样。执行 k 轮时，灯编号 x 被按到的次数等于 x 在 1 到 k 范围内的约数个数。注意，是"不超过 k 的约数"，而不是所有约数。举例：k = 3 时，编号 6 的灯约数是 1、2、3、6，但前三轮只会按到第 1、2、3 轮，所以 6 被按了 3 次，熄灭变成亮。这时候结论不再是简单的完全平方数，因为 6 不是平方数，但它在受限范围内约数个数是奇数。

这种变体的通用解法是：对每个编号 x，枚举其不超过 k 的约数个数，判断奇偶。复杂度偏低效，但笔试中 k 和 n 往往不大。如果追求高效，需要用到容斥和数论分块，普通岗位笔试一般不会考这么深。我的建议是：遇到这种变体，先写出暴力验证，然后观察 k 较小时的亮灯编号序列，找规律再优化，拿到基本分最重要。

4.2 变体二：只问你某一盏灯最后亮不亮

有些题目会砍掉统计部分，直接问：编号为 x 的灯在 n 轮之后是什么状态？这类题反而比原题更简单，因为只需要判断一个数。核心还是那一步：判断 x 是否为完全平方数。如果是，亮；否则，灭。

但这里有个陷阱：如果题目说的是"n 轮"而 n 小于 x，那么第 n 轮之后，编号 x 的灯有没有被按到取决于 x 的约数中有没有小于等于 n 的。此时答案不是简单的平方数判断，而是"x 的小于等于 n 的约数个数是否为奇数"。我见过不止一次候选人在这上面栽跟头，因为他们默认 n 足够大，直接把结论套上去。笔试时遇到这类问题，先确认 n 和 x 的相对大小，再决定用哪个结论，这是保命习惯。

4.3 变体三：灯泡初始状态不是全灭

还有些题目会做文章：初始状态部分灯亮着，或者问你经过 n 轮之后有几盏是灭的。这类问题的处理方式是把"翻转"看作异或操作，初始亮着的灯相当于先被按了一次。最终状态由初始状态叠加翻转次数共同决定。如果初始亮且被按奇数次，最终灭；初始亮且被按偶数次，最终亮。需要针对初始状态单独分情况统计。

应对这种变体，我的建议是画一张真值表，把"初始状态 × 操作次数奇偶"的四种组合列出来，然后对每盏灯分类。笔试时间充裕的话，完全可以对部分数据暴力验证。这类题考察的是你有没有真正理解状态翻转的本质，而不是背结论。

4.4 变体四：区间查询与批量统计

进阶一点的笔试题会问：给定一个区间 [L, R]，问这个区间里最终亮着的灯有几盏。本质是统计区间内完全平方数的个数。答案就是 floor(sqrt(R)) - floor(sqrt(L - 1))。这个公式不难，难在区间端点处理，尤其是 L = 1 时，floor(sqrt(0)) 是 0，不会出错，但有人会写成 floor(sqrt(L))，导致边界偏差。

我踩过一次坑，当时算 [4, 9] 的答案，用错误的公式得到 2，实际应该是 3（4、9 两个平方数加一个边界，等下，[4,9] 里平方数是 4 和 9，还是 2，没算错）。让我换个例子说清楚，区间 [1, 4] 的平方数是 1 和 4，正确答案是 2；如果写成 floor(sqrt(4)) - floor(sqrt(1)) = 2 - 1 = 1，就错了。正确公式要用 floor(sqrt(R)) - floor(sqrt(L - 1)) = 2 - 0 = 2。这个细节值得专门记下来，边界处理是笔试判分最容易漏的地方。

5. 这些坑我踩过，写出来给你避雷

5.1 浮点开根号的精度问题

sqrt(n)返回的是浮点数，在 n 特别大时可能因为精度误差向下取整出错。我一个同事曾经测试过，某些大整数在部分编译器上(int)sqrt(n)会得到比真实平方根小 1 的结果，原因就是浮点数无法精确保存大整数。所以我在代码里始终坚持用整数平方根函数。

C++ 在 C++11 标准后可以用sqrtl配合long long勉强缓解，但最稳妥的是自己写二分或直接用sqrt后再验证(m+1)^2 <= n是否成立。Python 里用math.isqrt就好，Java 里可以用(int)Math.sqrt(n)然后同样做一个矫正。这个矫正步骤在笔试中写不写都能过绝大部分用例，但当 n 接近 10^18 时，它决定你是 AC 还是 WA。

5.2 数据类型的溢出

原题 n 的范围有时候给到 10^9，有时候给到 10^18。第一种用 int 没问题，第二种必须用 long long。问题出在有些人返回sqrt(n)时强转 int，导致数值被截断。再有就是我在算 m^2 验证边界时，m 本身是 long long，但 m 的平方可能超过 int 范围，必须用 long long 承接。

这里我有一个实操习惯：凡是题目没有明确说明 n 的上下限，写代码时一律用 long long，返回值类型也尽量用 long long。笔试的判题系统对溢出非常敏感，一个 int 的溢出可能让你在一道送分题上丢一半分数，这太不划算了。

5.3 边界的魔鬼细节

n = 0 的时候，一盏灯都没有，答案应该是 0，isqrt(0)返回 0，天然正确。n = 1 的时候，只有第一轮按了灯，灯亮，答案是 1，isqrt(1)返回 1，也正确。很多人会担心边界，但这题用isqrt几乎天然免疫边界问题。反而是修改过的变体容易出错，比如区间统计那个，差一个 1 就看不出对错，所以我的建议是每个变体都准备一个暴力对拍函数，随机生成小数据验证。

5.4 怎么在笔试中展示你的思考

这题代码太短，实际写完可能不到十行，所以阅卷更看重推导过程。我建议在代码注释里简要写清楚关键推导：灯 k 被按次数等于 k 的约数个数，约数个数的奇偶性与完全平方数等价。如果是线上笔试，允许的话就在代码前用注释写推导过程；如果是手撕代码，先在白板上画一盏灯的约数配对，再写代码。

我已经用实际行动验证了这个展示逻辑：我出过一套模拟笔试，两道题，一道是灯泡开关，一道是普通的字符串处理。交卷后看记录，写下"约数成对"四个字的候选人，平均得分明显高于只写代码的人。这不是玄学，而是阅卷人能直观看到你的思考深度，分自然就给得松。

6. 一道小题背后的通用方法论

6.1 从这道题总结出"操作模拟"类题目的通用套路

灯泡开关不是一个孤立题型。凡是题目说"某人或某个规则反复作用在某些元素上"，都可以套用同一套分析框架：确定每个元素被作用的次数；分析次数奇偶性带来的状态变化；寻找次数分布的数学规律；利用规律直接计算答案。

这个框架我后来用在"开关灯""翻牌""翻转硬币"等一堆题目上，屡试不爽。甚至 LeetCode 上那道"翻转字符串中的单词"如果用这个思路去审视，也能找到类似的规律化处理路径。所以我说，刷题不要只看题解，要把方法沉淀成自己的分析框架，这样遇到新题才不会慌。

6.2 平方数结论的直觉记忆法

如果你担心自己考场上一时想不起"约数个数奇偶 ⇔ 完全平方数"，我给你一个记忆锚点：想象 4 和 6 这两盏灯。4 的约数是 1、2、4，中间有个"自己配自己"的 2；6 的约数是 1、2、3、6，两两配对刚刚好。每一个平方数都自带一个"中心约数"，正是这个中心，让约数个数从偶数变成奇数。

这个记忆法我分享过很多人，反馈都说比死记结论深刻。考试时如果脑子一片空白，就从一个小平方数比如 9 开始，手动推它的约数：1、3、9，发现是奇数个，顺着这个感觉推下去，很快就能想起来完整的推导链。我用这种方式在好几次模拟面试里帮候选人稳住了心态。

6.3 后续还可以怎么扩展

这道题看起来到头了，但往深处还能延展：如果操作不是"翻转"而是"从某轮开始只操作质数编号"，结果会变成什么样？如果灯的初始状态不是全灭而是随机，怎么用期望来算亮灯数量？如果 n 轮只操作一半而另一半不操作，结果如何分段表达？这些变体在面试官追问环节非常常见，平时多想想，面试就不会被问穿。

我个人最喜欢的一个扩展是"双重翻转"：第一轮按奇数编号，第二轮按所有编号，问最终状态。这种题目就是利用异或的交换律和结合律，把操作等价合并。做过灯泡开关之后再见到类似题，你会有一种"这道题我见过"的底气，这种底气来自你对原理的掌握，而不是背过多少个答案。

这个题目就是我常说的"披着模拟题外衣的数学题"，处理它的过程，比答案本身值钱得多。