《信息学奥赛一本通》第5章的 2036 这道题名字叫“开关门”是我带训练队时每次都要讲的例子。原因很简单它代码量极小但如果你只是模拟着把题过了就白白浪费了一次建立“约数模型”的机会。这道题适合两类人刚学完循环、想练数组和取反的新手以及刷题一段时间、想提升“从暴力到规律”这一层思维的同学。看完这篇你不光能AC 2036还能顺手秒掉一大类类似题。先说结论这道题表面上是“循环套循环”的模拟题骨子里考的是“约数个数”的奇偶性。最终开着的门一定都是完全平方数编号。为什么往下看。1. 先把题意彻底嚼碎1.1 题目到底让你干什么题目描述不复杂说的是一个宾馆里有 n 个房间编号从 1 到 n一开始所有门都是关着的。第 1 个人把所有门都打开第 2 个人把编号为 2 的倍数的门做相反处理也就是开着的关上、关着的打开第 3 个人把编号为 3 的倍数的门做相反处理这样一直下去直到第 n 个人把编号为 n 的倍数的门做相反处理。输入就一个整数 n范围是 2 到 1000。输出的是最后还开着的门的编号编号之间用空格隔开。这里有一个非常关键的建模视角第 1 个人“把所有门都打开”其实可以等价看成“把编号为 1 的倍数的所有门做相反处理”。因为初始状态全是关的把 1 的倍数全部翻转一次结果就是全开。这样一统一整道题就变成一个非常规整的规则第 i 个人负责把编号是 i 的倍数的门全部翻转一次。这个统一的建模方式后面写代码时会省很多事。1.2 拿 n10 手推一遍全流程为了不让自己晕在抽象规则里我们先手动推一遍小数据。假设 n10一共 10 个门初始全关。我列一张表把每个门被哪些人操作、操作了几次、最后是开还是关都写出来。这张表非常值得你亲手推一遍推完你对题意的理解就不一样了。门编号被哪些人操作操作次数最后状态111开21, 22关31, 32关41, 2, 43开51, 52关61, 2, 3, 64关71, 72关81, 2, 4, 84关91, 3, 93开101, 2, 5, 104关n10 时最后开着的门是 1、4、9。这三个数的共同点一眼就能看出来它们都是完全平方数。1 是 1 的平方4 是 2 的平方9 是 3 的平方。这当然不是巧合。但为什么完全平方数就会开等到第 3 节我再详细证明。现在先想想如果不知道这个规律代码该怎么写。2. 第一反应暴力模拟怎么实现2.1 用一个布尔数组模拟每个门模拟的思路非常直接用一个布尔数组door[]表示每个门的状态false表示关true表示开。每次操作就是把这个位置的值取反。取反在 C 里写法有好几种最常见的是door[j] !door[j];或者用位运算door[j] ^ 1;。这两种都能达到目的我个人更喜欢后者因为看起来更“翻转”一点而且对新手来说异或 1 这个操作本身就是开关切换的经典模型。有一个特别容易踩的坑是数组初始化。如果你把bool door[1005];定义在 main 函数外面也就是全局变量区那么它会被自动初始化为false也就是全关状态这不影响正确性。但如果你把数组定义在 main 函数里面不做初始化的话里面的值是不确定的运行结果就会乱七八糟。很多新手第一次写这道题在本地跑出来全是开着的门十有八九就是忘了初始化局部数组。我建议新手阶段直接写成全局数组省心又安全。题目里 n 最大 1000那么bool door[1005]就够用了。下标 1 到 n 表示真实的房间下标 0 空着不用这样能避免“编号和下标错一位”的经典问题。2.2 关键选择从“判断整除”改成“倍数跳跃”模拟嵌套循环时新手第一版通常写成这样外层循环 i 表示第 i 个人内层循环 j 遍历 1 到 n 的所有门然后判断if (j % i 0)再取反。for (int i 1; i n; i) { for (int j 1; j n; j) { if (j % i 0) { door[j] !door[j]; } } }这段代码对不对完全正确。n 最大只有 1000所以它跑得动交上去也能过。但它的时间复杂度是 O(n²)也就是最坏要执行约一百万次判断。这个规模在题目限制下没事但你要意识到这种写法的问题在于“把所有门都看一遍再一个一个判断是不是 i 的倍数”。更好的写法是换一个角度既然第 i 个人只会碰到编号为 i、2i、3i……的门那我直接从 i 开始每次加 i专门跳着访问这些门就行了不需要碰那些不是倍数的门。for (int i 1; i n; i) { for (int j i; j n; j i) { door[j] !door[j]; } }得仔细说说j i这一步。它的意思是j 从 i 开始然后是 ii 也就是 2i再到 3i一直加下去直到超过 n。这正好覆盖了所有“编号是 i 的倍数”的门。比如 i2 时j 依次是 2、4、6、8、10i3 时j 依次是 3、6、9。这种“倍数跳跃”写法的复杂度是多少总的操作次数是 n/1 n/2 n/3 ... n/n也就是 n 乘以调和级数 H(n)。学过基本复杂度分析的话应该知道这个和约等于 n log n。n1000 时大概只有七千多次操作比一百万多得多。这个优化不是靠什么高级技巧而是靠理解了“人在操作门”这件事本身的规律。2.3 可以直接 AC 的模拟代码无论你用整除判断还是倍数跳跃都能 AC 这道题。但如果想给后面的规律做铺垫我强烈建议用倍数跳跃版本。完整代码如下#include iostream using namespace std; bool door[1005]; int main() { int n; cin n; for (int i 1; i n; i) { for (int j i; j n; j i) { door[j] !door[j]; } } bool first true; for (int i 1; i n; i) { if (door[i]) { if (!first) cout ; cout i; first false; } } cout endl; return 0; }注意输出部分我用了一个first变量来控制空格。有些 OJ 对行尾多出来的空格不敏感但也有一些会严格比较所以养成“第一个输出前不打印空格之后每个数前打印一个空格”的习惯能帮你省掉很多无谓的罚时。这段代码交到任意一本通 OJ 上都能过。但如果你只满足于这个版本那就亏了。接下来才是这道题真正值钱的地方。3. 藏在背后的数学规律约数个数决定命运3.1 每个门被碰了几次答案在约数里把 n10 的表再拿出来看一遍。门 6 被操作了 4 次分别是第 1、2、3、6 个人碰了它。门 8 被操作了 4 次分别是第 1、2、4、8 个人。发现没有门 6 的约数是 1、2、3、6门 8 的约数是 1、2、4、8。第 i 个人会去碰门 k当且仅当 i 能被 k 整除也就是说i 是 k 的一个约数。所以一个非常干净的结论出来了编号为 k 的门在整个过程中被翻转的次数恰好等于 k 的正约数个数。这不是什么高深的数论就是一个定义层面的理解。题目里“第 i 个人操作 i 的倍数”这句话换到门 k 的视角看就是“所有能整除 k 的人都会来碰我”。一个简单的视角转换就把整道题的模拟过程抽象成了算术问题。3.2 为什么只有完全平方数是开着的现在问题变成哪些数的约数个数是奇数想一想约数是怎么成对出现的。如果 d 是 k 的约数那么 k/d 也一定是 k 的约数。比如 k12约数有 1 和 12、2 和 6、3 和 4每两个配成一对。只要 d 不等于 k/d那么约数一定是两个两个出现的总数是偶数。那什么情况下会出现“单独一个”的约数只有当 d k/d 的时候。这个等式成立的条件是 d² k也就是 k 是完全平方数d 等于根号 k。比如 k9 时约数是 1、3、9。1 和 9 配一对3 自己跟自己配对没法拆成两个不同的约数所以约数总个数是奇数。把这两件事连起来就得到了最终规律门 k 被翻转的次数等于 k 的约数个数。约数个数为奇数当且仅当 k 是完全平方数。翻转奇数次的门从初始的“关”变成“开”。所以最终开着的门恰好就是完全平方数编号的门。这个推理用一句话概括就是开关门的结果不取决于“过程”只取决于“每个门的约数个数的奇偶性”。而这个奇偶性由“是不是完全平方数”决定。3.3 先猜规律再证明竞赛找规律的标准节奏很多人第一次做这题时根本想不到约数。这不丢人。重要的是要知道用什么流程把它“试出来”。我的习惯是拿到这种和“倍数”“翻转”“状态切换”有关的题先不急着写证明先拿小数据打表。哪怕用最暴力的模拟把 n20 的结果打出来看一眼#include iostream using namespace std; bool d[25]; int main() { int n 20; for (int i 1; i n; i) { for (int j i; j n; j i) { d[j] !d[j]; } } for (int i 1; i n; i) { if (d[i]) cout i ; } return 0; }运行结果1 4 9 16。四个数。全是平方数。看到这个结果你立刻就能猜到规律开着的门 完全平方数。接下来再验证一下 n30 或者 n100如果还是 1、4、9、16、25、36、49、64、81、100那基本就坐实了。最后一步才是数学证明。这一步如果你推不出来在竞赛里其实也能把答案“猜”出来写上去但能证明就多了一层把握。竞赛找规律的标准节奏就三个词小数据打表、直觉猜结论、严格验证。4. 优化后的终极代码与复杂度对比4.1 从模拟到数学三行代码解决知道最后开着的门都是完全平方数之后代码量会小到让人怀疑人生。直接输出 1 到 n 之间的所有完全平方数即可连数组都不需要。#include iostream using namespace std; int main() { int n; cin n; bool first true; for (int i 1; i n / i; i) { if (!first) cout ; cout i * i; first false; } cout endl; return 0; }这个循环跑了多少次假设 n1000i 从 1 开始到 i31 时 ii961 还没越界i32 时 32321024 已经超过 1000循环结束。也就是说只执行了 31 次。时间复杂度是 O(√n)连 O(n) 都不到。输出的时候按 i 从小到大所以开门的编号自然就是 1、4、9、16……用first控制空格。这个版本扔到一本通里一样 AC。4.2 两种做法的时间和空间对比把三种写法的对比列出来你会更清楚每种方案的位置在哪里。方案时间复杂度空间复杂度代码量适用场景整除判断模拟O(n²)O(n)较短数据小、验证思路倍数跳跃模拟O(n log n)O(n)短n 在 10^6 以内完全平方数直接输出O(√n)O(1)极短任意规模一本通原题 n 最大只有 1000所以三种都能过。但如果你把 n 改成 10^6O(n²) 的写法必超时把 n 改成 10^12连 O(n) 都不能接受只有 O(√n) 的数学解法还能轻松跑完。这就是“从暴力到规律”的意义所在不只是为了这道题而是为了以后遇到大数据范围时的生存能力。4.3 边界条件与整数溢出问题数学解法虽然短但有一个细节值得注意循环条件到底写i * i n还是i n / i两者在数学上等价但工程上有个差别。i * i是整数乘法如果 n 很大比如 n 是 10^9i 最多到 31623乘积大概是 10^9int 还能扛住。但如果 n 是 2.5×10^9i 到 50000 时i * i就已经溢出 int 了结果变成负数循环条件直接失效。最稳妥的写法是用i n / i不乘只除永远不会有溢出风险。或者把 i 定义成long long那i * i n也安全。一本通这题 n 只有 1000溢出不会发生但把这个习惯从入门阶段就养好以后做大数据题会少踩很多坑。这里顺便记两个可以直接用的结论满足条件的开门数量是floor(sqrt(n))个其中第 k 个开着的门编号是 k²。后面扩展题里会用到。5. 我在实战中踩过的坑和排查技巧5.1 数组越界与初始化本地正常OJ 随机错这题数据范围小数组越界的问题不太明显但我在实际教学里见过太多类似情况必须提醒一下。一个经典错误是数组定义成bool door[1000]然后循环里访问door[1000]。在 C 里下标从 0 开始door[1000]已经越界了。很多编译器不报错运行时访问的是数组后面那块内存结果完全不可预测本地可能是 0OJ 上就变成随机值。最后的输出时对时不对是最难排查的一种问题。我的建议是涉及 1 到 n 编号的问题数组一律开成n 5或者常量多开一点。题里 n 最大 1000就开bool door[1005]宁可浪费几个字节也不要去踩越界的雷。另一个坑是局部数组初始化。这样写int main() { bool door[1005]; // 局部数组值不确定 // 直接使用 door[j] !door[j] 就是炸弹 }局部数组里的值是栈上的残留数据不一定是 0。要么在定义时bool door[1005] { false };要么用循环手动清零要么干脆挪到全局。全局变量默认零值这是 C 给懒人的福利好好利用。5.2 翻转写成赋值全开门的诡异 bug有一个错误特别隐蔽把door[j] !door[j]写成了door[j] true。表面上看都是“打开门”但前者是取反后者是强制设为开。如果我第 1 个人把所有门都强行设成 true那没问题第 2 个人再遇到 2、4、6……这些门本来应该把开着的关上结果又写成 true门永远关不上。最后程序输出的就是 1 到 n 所有编号看起来“全是开着的”。遇到这种输出第一反应就是检查是不是把取反写丢了。用位运算door[j] ^ 1;能减少这种错误的发生因为异或这个操作没有别的含义就是翻转。建议新手在写“开/关”“是/否”切换时养成用异或 1 的习惯。5.3 如果题目改成“初始门全开”理解了模型之后随便改条件都不怕。我经常给学生留一个变形如果所有门一开始是开着的其他规则完全一样最后哪些门是开着的推理一下完全平方数编号的门约数个数是奇数会被翻转奇数次从“开”变成“关”非完全平方数的门约数个数是偶数翻转偶数次从“开”保持“开”。所以答案是除了完全平方数之外的所有门都开着。这个结论如果写代码也不复杂#include iostream using namespace std; int main() { int n; cin n; bool first true; int t 1; for (int i 1; i n; i) { if (i t * t) { t; continue; // 完全平方数最后是关着的跳过 } if (!first) cout ; cout i; first false; } cout endl; return 0; }这个变形的意义在于它验证了你是不是真的理解了“翻转次数奇偶性”这个核心模型而不是死记“开着的门是完全平方数”。6. 这道题还能带给我们什么6.1 从开关门到倍数跳跃与筛法“倍数跳跃”这个写法在算法竞赛里比这道题本身重要得多。最典型的就是埃拉托斯特尼筛法找某个范围内的质数时核心循环长这样for (int i 2; i * i n; i) { if (isPrime[i]) { for (int j i * i; j n; j i) { isPrime[j] false; } } }你看这个j i的结构和开关门里的j i是不是一模一样它们共同的内核是批量处理某个数的倍数。在处理“所有数的倍数”时总复杂度是 O(n log n)而不是 O(n²)。很多初学者学筛法会觉得这是新知识其实早就在开关门里见过了。如果你能把“倍数跳跃”形成一个条件反射以后再遇到约数倍数相关的问题思路会开阔很多。6.2 那些看着像模板的题怎么抓住本质在搜“信息学奥赛一本通 2036”的时候经常看到关联词里混着各种算法名词比如弗洛伊德、迪杰斯特拉之类。这道题和它们没有半点关系它考的是最基本的循环嵌套和数论观察。这提醒我一件事刷题千万别只看题目名字。看到“开关门”就以为是模拟题看到“路径”就以为是图论题这种“看名猜算法”的习惯很危险。正确做法是盯住两个信息数据范围和操作规则。如果 n 很小暴力模拟通常可行。如果 n 很大那必然存在某种规律让答案不需要完整枚举就能算出来。操作的规则往往决定了数学结构。这里的“倍数反转为奇数或偶数次”直接指向约数个数。竞赛里最值钱的能力不是背模板数量而是能从规则里提炼结构。开关门这道入门题就是个非常标准的结构提炼样本。6.3 给你几个“开关门”变形练练手理解了原理你可以自己扩展出一系列变式题打开思路。我列几个方向。第一初始状态全开问最后哪些门开着。答案是“非完全平方数”上面已经给过代码。第二n 变得非常大达到 10^15。这时候连 O(n) 都不能考虑直接用 O(√n) 输出平方数即可代码和数学解法一模一样只需要注意long long。第三不要求输出所有开着的门只问你第 k 个开着的门的编号。答案是 k²直接输出即可连数组和循环都不用。第四给一个具体号码 m问某扇门最后是什么状态。判断 m 是不是完全平方数就行也就是检查sqrt(m)是否为整数。这四种变形全部基于同一个核心模型操作次数等于约数个数约数个数的奇偶性决定最终状态。能把一道题从多个角度变着玩才算真正吃透了。我个人在教学时的体会是这题最适合拿来培养“先暴力、再打表、后证明”的解题节奏。很多学生刷题时习惯一上来就写最优解结果卡住了反而浪费时间。先写一个暴力版本跑通再用小数据猜规律最后用数学把规律坐实这套流程在竞赛里能救你很多次。开关门这道题不复杂但把这个流程完整走一遍你收获的就不只是 AC 一个题目而是一整套可复用的分析问题的方法。