灯泡开关问题的数学优化：从暴力循环到O(1)常数级解法

题目叫“高性能计算笔记灯泡开关问题的数学优化与常数级解法”先别被“高性能计算”四个字唬住。这个经典题本身很简单就是在100盏灯、100轮开关的设定里第i轮翻转所有编号为i的倍数的灯泡问最后哪些灯亮着。可它背后那条数学链路从暴力循环一路走到常数级判定才是真正值得反复琢磨的东西也是高性能场景里最常遇到的思维模式能用数学化简的绝不靠循环硬算。我最初接触这个题是在一次算法面试热身里后来发现很多刷题网站、竞赛入门题都喜欢拿它当“简单题”处理。但简单题不等于没有价值。恰恰是这种题目能把约数理论、奇偶性分析、复杂度优化串起来讲透对准备面试的人、写底层工具的人、甚至做数值仿真的人都很有用。这篇笔记不打算只给结论我想把“灯泡开关问题”从最朴素的实现开始一步步演化到 O(1) 判定和 O(√n) 构造答案的完整思路并顺带聊聊延伸变体和实际工程里会踩的坑。无论你是在校学生、算法爱好者还是写高性能服务的工程师这套分析过程都值得看下去。1. 开场这个经典题到底在考什么先把题目再明确一遍因为网上流传的版本太多有100盏灯、100个人的也有n盏灯、n轮的通用版。为了后面推导方便我统一用通用描述有 n 盏灯初始全部熄灭第 i 轮i 从 1 到 n将编号能被 i 整除的所有灯做一次状态翻转亮变灭、灭变亮最终统计哪些灯处于亮着状态。一眼看过去这就是个模拟题甚至不需要动脑。但真正参加过面试或者自己动手写过的人会有感觉模拟能做问题是当 n 变大时模拟的成本会迅速失控。假设 n 100内层总操作次数大约是 n × (1/1 1/2 ... 1/n) ≈ n ln n也就是几百次毫无压力。可换成 n 10^7 或 10^8模拟一次可能要跑几十秒甚至更久内存还要开一个 n 大小的布尔数组在资源敏感的应用里这就是灾难。所以这个题真正想考察的不是你会不会写两层循环而是你愿不愿意停下来想想每个灯泡到底被翻转了多少次这个“翻转次数”背后有没有规律一旦想通了这个问题就从“需要遍历所有轮次”变成“只需要判断一个数是否为完全平方数”直接跨到常数级解法计算量可以被压缩到几乎为零。这也是我为这篇笔记标题加上“高性能计算”的原因高性能并不是指把循环写得多漂亮而是指找到一种计算模型让很多原本要执行的操作在数学上被抵消掉。接着我会从最笨的方法开始写相信我这个演进过程比最终结论有意思得多也是理解“常数级解法”的一把钥匙。2. 暴力解法与复杂度的第一层优化2.1 双层循环的暴力版本先给最直白的实现思路开一个长度为 n1 的布尔数组初始全 false表示灯灭然后从 i 1 到 n 遍历轮次内层从 j i 到 n每次步进 i把灯 j 的状态取反。用 JavaScript 写就是这样。function lampsBruteForce(n) { const lights new Array(n 1).fill(false); for (let i 1; i n; i) { for (let j i; j n; j i) { lights[j] !lights[j]; } } const result []; for (let k 1; k n; k) { if (lights[k]) result.push(k); } return result; }这段代码逻辑没毛病也算好懂。但它的总操作次数是 n/1 n/2 ... n/n n × H(n)其中 H(n) 是调和数约等于 ln n γ。时间复杂度是 O(n log n)空间复杂度 O(n)。当 n 是 10^5 时很轻松n 到 10^7 开始喘n 到 10^8 基本就得等好一会儿了。我实测过一次在本机跑 n 10^8两层循环的版本大概要 6 到 8 秒内存还要 100MB 左右的布尔数组。纯粹为了拿答案这太奢侈了。如果放在一个实时性要求高的系统里哪怕只是让用户等 0.5 秒这种实现都会被直接打回。2.2 单层循环统计切换次数稍微想一下我们其实并不关心过程只关心每盏灯最终是亮还是灭。而亮灭取决于这盏灯被翻转了多少次翻转奇数次则亮翻转偶数次则灭。于是问题可以改成“统计每个编号有多少个约数”。代码可以写成下面这样虽然时间复杂度没降但省掉了一个大数组的反复写入常量因子小了很多。function lampsCountDivisor(n) { const result []; for (let k 1; k n; k) { let cnt 0; for (let d 1; d * d k; d) { if (k % d 0) { cnt (d * d k) ? 1 : 2; } } if (cnt % 2 1) result.push(k); } return result; }这个版本已经是“先简化模型再优化实现”的思路了不去模拟每一轮翻转而是直接把约数个数算出来。可如果你真的把代码跑一遍会发现它依然是 O(n√n) 的复杂度——对每个 k 都要枚举到 √k总共 O(n√n)比原始的双层循环还慢。问题出在哪里出在“枚举约数”这个动作本身不便宜。所以真正的优化从来不是换一种同样规模的计算方式而是找到一种方法直接跳过绝大多数计算量。这也正是第三部分要讲的数学结构约数配对与完全平方数。3. 核心数学优化约数配对与完全平方数3.1 约数的成对出现灯泡状态和约数个数之间建立联系之后我们只需要回答一个问题什么时候一个数的约数个数是奇数先从直觉入手。任取一个正整数 n如果 d 是 n 的约数那么 n/d 也一定是 n 的约数。比如 12 的约数有 1、2、3、4、6、12我把它们两两配对1×122×63×4正好配成 3 对所以 12 有 6 个约数是偶数。这个“成对出现”的性质几乎对所有数都成立唯一的例外发生在 d n/d也就是 d² n 的时候这时 d 和自己配对只算一个约数而不是两个。生活化一点可以想象大家在排队找搭档组合大多数人的搭档都能两两配好只有站在正方形中心的那个人只能和自己组队于是总人数就是奇数。这个“中心点”对应到整数里就是完全平方数。3.2 奇偶性与亮灯判定有了上面的结论整道题的答案就浮出水面了编号为完全平方数的灯约数个数是奇数个其余编号的灯约数个数是偶数个。因为约数个数等于被翻转次数而翻转奇数次意味着灯亮着所以最终亮着的灯恰好就是 1, 4, 9, 16, 25 ... 这些完全平方数。用 n 100 代入亮着的灯号是 1, 4, 9, 16, 25, 36, 49, 64, 81, 100正好 10 盏。跑一个简单的验证脚本就能确认。import math def last_lights_on(n): ans [] for i in range(1, n 1): d int(math.isqrt(i)) if d * d i: ans.append(i) return ans print(last_lights_on(100)) # [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]这段代码里我用 isqrt 而不是 sqrt就是为了避免浮点误差。它能直接验证理论结论和真实模拟完全一致而且速度比你写任何两层循环都快。到这里“灯泡开关问题”已经从模拟题变成了一道数学判断题。3.3 数学分析的高性能意义有读者可能觉得所以呢不就是鉴了个完全平方数吗千万别小看这一步。它直接把问题的性质改变了。原来我们要维护一个长度为 n 的状态数组反复翻转数据现在只需要对每个编号做一次完全平方判断甚至不需要构造数组。随着 n 增大内存从 O(n) 降到 O(1)计算量从 O(n log n) 降到 O(n)而且每盏灯的判定是常数时间。在实际工程里“把一个问题降复杂度”往往比“把同复杂度代码优化 20%”重要得多。举个例子如果你在百万级数据管道里做某个状态筛选用满内存的数组模拟和用数学判定直接筛选前者可能拖垮整个节点的资源后者连一个缓存行都用不满。这也就是为什么很多高性能计算领域的老手遇到数学相关问题时第一反应是找闭式解而不是拼命调循环。4. 常数级解法直接构造答案4.1 从“判断每盏灯”到“枚举平方数”既然最终亮着的灯都是完全平方数那与其遍历 1 到 n再逐个判断是否平方数不如直接从 1 开始枚举 i输出 i²直到 i² n。复杂度从 O(n) 进一步降为 O(√n)这个差距在 n 很大时非常恐怖。比如 n 10^12O(n) 可能要几分钟O(√n) 只要几毫秒。单盏灯的判定仍然可以做到 O(1) 常数级这也是标题里“常数级解法”的由来给任意一个编号 k判断这盏灯最终是否亮着就是判断 k 是否为完全平方数一步数学运算搞定不依赖 n 的大小。代码也非常短。function solution(n) { const ans []; for (let i 1; i * i n; i) { ans.push(i * i); } return ans; }这个版本没有任何数组状态的维护没有轮次循环只有一次幂方比较。两个核心点i * i 可能溢出需要用安全的乘法或 BigInt见常见问题部分枚举边界是 i * i n也就是 i √n不是 i n。4.2 为什么叫“常数级解法”我先把术语边界说明白免得读者被“常数级”误导。严格来说如果问题是“给定 n列出所有亮着的灯的编号”那答案有约 √n 个必然至少需要 O(√n) 的输出量不可能做到 O(1)。但如果是“给定 n 和 k问第 k 盏灯最后亮不亮”那这道题的解法确实是 O(1)判断 k 是否为完全平方数。所以最好的描述是算法对“单点查询”是常数级对“枚举全部答案”是 O(√n)。这个区别在做技术方案评审时一定要讲清楚不然容易被追问“你 O(1) 怎么还要循环输出答案”。提示面试和文档里最好明确写“常数时间查询O(1)枚举答案O(√n)”避免沟通成本。很多“高性能”方案其实都踩过类似的坑把常见操作的复杂度降下来却忽略了 IO 或输出量才是真正的瓶颈。这个问题里最后的瓶颈就是输出本身这绝不是坏事反而说明计算已经被优化到了几乎没有存在感。4.3 大 n 下的表达式与格式化输出当 n 很大比如 10^16你确实可以用 O(√n) 的时间把所有平方数枚举出来但直接把它拼成一个巨大的字符串再一次性打印依然会引发内存和 IO 问题。如果只是要逐行输出到文件建议流式写入不要先 build 一个巨大的数组。const fs require(fs); const out fs.createWriteStream(lamps.txt); function writeSquareLamps(n) { for (let i 1; i * i n; i) { out.write(String(i * i) \n); } out.end(); }如果你需要的是“第 m 个亮灯泡是谁”那题目就变成了寻找第 m 个完全平方数答案就是 m²。此时连枚举都不需要直接 O(1) 给出结果。这也是常数级解法的一个实际应用把“位置”映射到“值”不需要遍历任何东西。高性能计算里经常有这种操作把枚举类问题翻译成解析类问题让答案直接从公式里长出来。这种思维一旦养成你会开始习惯性地寻找问题的数学结构而不是急着写循环。5. 延伸变体从灯泡到更广的数学结构5.1 异或视角与奇偶校验灯泡开关本质上就是二进制状态的翻转所以它天然和异或运算有关。如果把每盏灯看成一个 bit第 i 轮等价于把所有 i 的倍数对应的 bit 异或 1。最终状态就是整个过程中该 bit 异或 1 的总次数也就是约数个数的奇偶性。完全平方数的约数个数为奇因此最终状态为 1其他数为偶最终状态为 0。这个视角在硬件层面很有意思它对应一个非常轻量的奇偶校验电路你不需要真正构建开关矩阵只需要用约数奇偶性作为判断条件。在做低资源嵌入式开发时这种“化算力为数学”的思路可以省下不少逻辑门数和存储空间。我在一个开源项目里看到过类似的推广把“每个点被访问次数是否奇数次”抽象成问题直接靠数学判断而不是维护全局状态的往往在数据规模上去后依然能保持极低延迟。这也是“高性能计算笔记”这个题目的灵魂用静态分析替代动态模拟。5.2 变体问题不同翻转频率与环形灯泡经典题可以轻松改成很多变体。比如只有部分轮次参与操作只翻转编号为质数的倍数轮或者灯排成一个环每轮翻转固定间隔的灯再或者某些灯一开始就是亮着的需要求最终状态。这些变体大多不能直接套用“完全平方数”结论但分析套路是相通的先把每盏灯受影响的操作次数表达出来再判断奇偶性。例如只有第 2、3、5、7... 质数轮参与时灯号 k 的翻转次数就是 k 的质数约数个数这时候就要数 k 的质因子族完全平方数的概念立刻不够用了。对大多数读者来说掌握基础版本的推导流程比背诵结论更有价值。真正面试或实战中怪异的变体往往就是把你逼回第一性原理让你现场从头推导。能写出“翻转次数 约数个数 奇偶性 → 平方数”这条逻辑链的人改一改就能对付一半变体。6. 常见问题与排查技巧实录6.1 浮点数 sqrt 与整数溢出的坑这道题代码很简单但真的动手写细节上还有不少暗坑。第一个坑是用 Math.sqrt 判断完全平方数。当 n 很大时浮点数的精度不够比如 sqrt(10000000000000001) 可能会被判成整数导致结果错误。正确做法是使用整数开方函数 isqrt或者自己写一个整数二分。Python 自带 math.isqrtJavaScript 可以写一个简单的整数二分或者先算整数部分再回乘校验。第二个坑是枚举平方数时的溢出。如果 n 接近 Number.MAX_SAFE_INTEGERi * i 会丢精度。在 JavaScript 中可以用 BigInt 或提前判断 i n / i避免中间结果越界。下面是安全的判断方式。function isPerfectSquare(k) { let lo 1, hi k; while (lo hi) { const mid Math.floor((lo hi) / 2); const sq mid * mid; if (sq k) return true; if (sq k) lo mid 1; else hi mid - 1; } return false; }这里最凶险的地方是 mid * mid 本身也可能溢出。要彻底防止可以改用除法mid k / mid而不是 mid * mid k。这个小细节很多刷题老手也容易漏。6.2 边界条件与输出顺序第二个常见的坑是 n 0、n 1 这些边界值。n 0 时没有灯泡答案为空n 1 时第 1 轮翻转第 1 盏灯亮着答案就是 [1]。用 i * i n 的写法这两者天然安全不需要特判。但如果你写 while (i Math.sqrt(n))浮点误差可能导致 n 1 时漏判这是我实测见过的情况。输出顺序也别搞错。枚举平方数的时候自然顺序就是从小到大但如果你用哈希集合去重后再输出反而可能丢失有序性。这道题不需要哈希不需要排序一个 for 循环就完了别画蛇添足。6.3 复杂度分析的口径还有一个经常被程序员挂在嘴边的坑把“平均复杂度”当“最坏复杂度”。如果你对每个 k 判断约数个数复杂度是 O(n√n)比较慢如果你用埃氏筛的思路直接预处理约数个数复杂度 O(n log log n) 或 O(n log n)但最优做法是避开约数枚举用平方数直出答案复杂度 O(√n)。三者差别极大讨论性能时一定要说清楚你用哪一种。注意如果面试官追问“除了完全平方数还有其他方案吗”不要慌。可以先承认这是最标准的结论然后提出可以用埃氏筛做预处理、用直方图统计约数个数但最终都会被数学优化压过。这反而是展示你对复杂度和备选方案理解得好机会。7. 个人体会与建议灯泡开关问题是我见过最适合用来练习“算法思维平移”的小题。它表面上是数组模拟中间是数论识别最后又落回高性能计算里常说的 closed-form 求解。我每次给团队新人讲这道题都会强调一句真正的高性能不是代码写得有多快而是当你发现这道题根本不需要模拟的时候代码里所有优化都显得多余。这几年的工作里我也经常遇到类似的“伪模拟题”。比如某个数据管线的状态轮转、某个游戏里的倍率叠加看起来要维护一大堆状态其实只需要把公式推出来几个乘法就结束了。学会识别这类结构之后你会从“读数据、换算、输出”的模式里解放出来把算力留给真正没有办法化简的部分。最后再分享一个小技巧遇到这类“轮转、切换、开关”的题目第一反应永远是问一句“每个元素的最终状态由什么决定”。如果答案是“被某个序列命中的次数”那就果断把计数问题拆出来再用奇偶性、周期、公式去收敛它。灯泡开关问题只是这条思路最清晰、最友好的一个入门案例但它的思维链路会伴随你很久。