“信息学奥赛一本通”的2036题【例5.3】开关门是我给刚学完数组和循环的OI新手必推的一道题。它看起来只是把n扇门翻来翻去最后统计哪些门开着可真正做明白之后你会发现它其实是“模拟转数学”的启蒙题。这篇文章我会从读题、手推、暴力模拟、数学证明到最终代码把整条思考链路拆开讲并把我带学生过程中遇到的常见错误一并列出来。不管你是刚开始刷一本通的小白还是想给学弟学妹讲题的学长这篇应该都能给你一点有用的东西。1. 题目到底在说什么从读题到样例推演1.1 题目大意三句话讲清楚这道题的题干一般长这样有n扇门编号从1到n初始全部关着。现在来了n个人第1个人把编号是1的倍数的门全部“反向操作”一次第2个人把编号是2的倍数的门全部反向操作一次第3个人把编号是3的倍数的门全部反向操作一次……一直到第n个人把编号是n的倍数的门反向操作一次。最后问哪些门是开着的。这里的“反向操作”是整道题的题眼门原来是关的就打开原来是开的就关上。用计算机的话说这就是一个翻转操作或者说toggle。很多新手一开始把它理解成“打开”或者“关闭”那后面推出来的结果就完全不是一回事了。输入是一个正整数n输出是最后开着的门编号从小到大排列空格隔开。拿n10来说最终答案是1 4 9。如果你自己手算一遍发现结果确实是这三个数那说明你对题意的理解基本到位了。1.2 手推n10的完整过程我不建议你上来就敲代码先拿笔推一遍n10比什么都管用。初始状态10扇门全关。第1个人操作1的倍数也就是1到10所有门都翻转一次结果1号到10号全开。第2个人操作2、4、6、8、10这五扇门从开变关结果奇数编号的门还是开着偶数编号的门全关了。也就是说现在开着的门是1、3、5、7、9。第3个人操作3、6、93从开变关6从关变开9从开变关。现在开着的门是1、5、7。第4个人操作4、84从关变开8从关变开。现在开着的门是1、4、5、7、8。第5个人操作5、105从开变关10从关变开。现在开着的门是1、4、7、8、10。第6个人操作66从开变关。第7个人操作77从开变关。第8个人操作88从开变关。第9个人操作99是关的翻转成开。第10个人操作1010从开变关。一路整理下来最后开着的门就是1、4、9。这个手推过程看起来很笨但它能帮你建立一个很重要的直觉每一扇门被翻转的次数不是随机的而是有规律的。第k号门从头到尾被翻转了几次你仔细一想只有那些“人是第k号门的约数”时这扇门才会被碰到。也就是说门k被翻转的次数等于k的正约数个数。1.3 这题背后真正想考的能力一本通把这道题放在“例5.3”说明它默认你已经会了循环、数组、条件判断这些语法层面的东西。它真正想考察的是两件事第一你能不能把一个自然语言描述的规则准确地转换成循环结构。这个属于基本功也就是“模拟能力”。第二你能不能跳出模拟看到藏在背后的数学规律把O(n²)的傻方法优化成O(√n)的聪明方法。这个属于“建模能力”。很多同学第一次做这个题能写对模拟版就已经很高兴了。但我建议你无论如何都要再想一步为什么答案全是平方数一旦你想通以后再遇到“开关灯”“翻转门”“反转硬币”这类题目你的第一反应就不再是闷头模拟而是先去想奇偶性、想约数个数。这就是竞赛思维和普通刷题思维的分水岭。2. 设计算法之前先想清楚复杂度与规律2.1 数组翻转模拟先拿基础分最直白的写法是这样的用一个bool数组表示每扇门的状态false表示关true表示开。外层循环枚举第i个人内层循环枚举i的所有倍数把对应门的状态取反。bool door[1005]; for (int i 1; i n; i) { for (int j i; j n; j i) { door[j] !door[j]; } }这个写法里内层循环的j从i开始、每次加i恰好覆盖i的所有倍数。它其实和“for (int j 1; j n; j) if (j % i 0)”完全等价但不需要取余判断代码更干净执行效率也更高。对于一本通这类入门题目n一般比较小这种模拟版完全能过。所以如果你是在巩固语法那就大胆用模拟写如果你是在备战竞赛也要先把模拟写出来验证一下自己的思路再考虑优化。2.2 复杂度分析为什么不能无脑上模拟模拟版的复杂度需要算一下。外层循环是n次第i次内层循环大约执行n/i次所以总的操作次数是n/1 n/2 n/3 ... n/n n × (1 1/2 1/3 ... 1/n)后面这个括号里的东西叫调和级数它的值大约是ln n。所以总复杂度是O(n log n)。当n10万时大概要做100万到200万次翻转还能承受当n1000万时已经接近上亿次就比较吃力了如果n是10的9次方甚至更大模拟直接没戏。这里要对比另一种“更暴力”的写法如果把内层循环写成了j从1到n每个j都判断一次j % i 0那复杂度就是O(n²)n1万就已经很卡了。所以同样是模拟内层用“步长i”和用“取余判断”差别很大这个细节很值得养成习惯。2.3 从操作次数到奇偶性的关键转向现在回到问题的本质。门k的最终状态只取决于一件事它被翻转的次数是奇数还是偶数。初始是关翻转奇数次就变成开翻转偶数次又回到关。那么门k被翻转的次数等于k的约数个数。这一步是整个题目的灵魂。举个例子门6的约数有1、2、3、6四个所以第1、2、3、6个人都会碰它翻转4次最终是关。门9的约数有1、3、9三个翻转3次最终是开。门10的约数是1、2、5、10四个翻转4次最终是关。所以原题被等价地转化成了这样一个数学问题在1到n的所有正整数里哪些数的约数个数是奇数接下来就是数学登场的时候了。3. 核心数学原理约数个数与完全平方数的关系3.1 约数为什么会成对出现任何一个正整数k如果d是它的约数那么k/d也一定是它的约数。比如12约数有1和12、2和6、3和4它们总是成对出现。这里可以举个生活化的类比你去找一个数的约数就像找人组队找到一个队员d就一定能在队伍另一头找到他的搭档k/d。绝大多数情况下这个队伍里的人数是偶数因为每找到一个人就自动配好一对。12的约数个数是6个也就是3对。30的约数有1、2、3、5、6、10、15、30一共8个4对。这些数都不会是最后开着的门因为它们被翻转了偶数次门的状态跟初始一模一样。3.2 只有完全平方数才有奇数个约数问题来了什么时候组队会落单答案是当d和k/d相等的时候也就是d k/d即k d²。这个时候这个约数是自己配自己队伍里就少了一个人总人数变成奇数。比如16的约数1和16是一对2和8是一对4和4是同一对。写出来是1、2、4、8、16一共5个其中4是“单身”的。所以16的约数个数是奇数16号门最后一定是开着的。用数学语言严格说一遍就是设d是k的约数则k/d也是k的约数。若d ≠ k/d这两个约数成对出现只有当k是完全平方数时会存在一个约数d k/d使得约数无法配对。所以“约数个数为奇数”和“k是完全平方数”是充要条件。3.3 数学结论落到输出只需要枚举平方数一旦有了上面的结论题目的答案就从“所有约数个数为奇数的门”变成了“所有完全平方数编号的门”。1到n范围内的完全平方数就是1²、2²、3²……直到⌊√n⌋²。所以代码只需要循环i从1到√n输出i × i即可。这比模拟版不知道快到哪里去了。这个结论还附带一个副产品最后开着的门总数就是⌊√n⌋。比如n10√10向下取整是3所以开3扇门n100答案是1、4、9、16、25、36、49、64、81、100一共10扇恰好等于√100。我强烈建议你自己验证一下n1和n16这两个边界n1时只有1号门开着n16时输出1、4、9、16。边界测通了代码基本就不会有逻辑硬伤。3.4 如果题目不是“翻转”结论还成立吗这里想多说一句很多题目看起来很相似但一个词不同结论就全变了。如果题目里写的是“第i个人把编号为i的倍数的门打开”而不是“翻转”那结果就变成所有门都开着因为第1个人已经把门全打开了后面的人对它没有任何影响。如果题目改成“第i个人把编号为i的倍数的门关上”那最终只有1号门开着因为第1个人打开它之后再也不会有别人碰它了。所以读题时一定要把“打开”“关上”“翻转”这三个词看清楚。翻转是一种“不管当前状态是什么都取反”的操作它天然和奇偶性绑定而“打开”“关上”是绝对状态没有奇偶性什么事。这也是我在给学生讲这道题时一定会强调的地方。4. 完整代码实现从模拟版到数学优化版4.1 C模拟版代码与逐行解读下面这份代码适合练习数组和循环也适合用来验证数学版的结论。#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 j 1; j n; j) { if (door[j]) { if (!first) cout ; cout j; first false; } } cout endl; return 0; }两个地方值得说明。第一door是全局数组自动初始化为false正好表示所有门初始关闭。如果你把它定义在main函数内部就一定要手动初始化否则数组里的值是随机的整个程序的行为都会变得不可预测。第二输出结果时我用了一个bool类型的first变量它保证两个数字之间只有一个空格行尾不会有多余空格。很多OJ对行尾空格很敏感多一个空格可能直接判Presentation Error。4.2 C数学版代码与溢出陷阱数学版的代码短到让人怀疑是不是漏了什么但它确实是正确且完整的#include iostream using namespace std; int main() { int n; cin n; bool first true; for (int i 1; i * i n; i) { if (!first) cout ; cout i * i; first false; } cout endl; return 0; }循环条件i * i n每次输出i * i。当n10000时i最多到100非常快。这里有一个常见的陷阱i * i可能会溢出。虽然本题n一般不大但如果你在别的题目里也要判断“i的平方是否不超过n”更稳妥的写法是i n / i。因为n / i不会溢出而且两者数学上完全等价。我见过不止一个同学在n很大的题目里因为i * i溢出而无限循环或死循环调试半天才发现就是越界问题。如果n的范围可能超过10亿建议把变量类型定义成long long这样i * i的安全范围会大很多。竞赛中的好习惯是拿不准数据范围时整数一律开long long能省掉很多不必要的麻烦。4.3 Python版与浮点精度问题Python写模拟版非常直观n int(input()) door [False] * (n 1) for i in range(1, n 1): for j in range(i, n 1, i): door[j] not door[j] ans [str(i) for i in range(1, n 1) if door[i]] print( .join(ans))需要注意door这个列表的长度是n 1这样下标才能从1用到n而不是从0到n-1。这算是Python新手经常踩的坑。Python写数学版也简单from math import isqrt n int(input()) ans [str(i * i) for i in range(1, isqrt(n) 1)] print( .join(ans))这里我特意用了isqrt而不是int(n ** 0.5)。因为浮点数的开方在某些边界情况下会有精度误差比如n是很大的完全平方数时int(n ** 0.5)可能会比真实平方根小1。isqrt是Python 3.8以后内置的整数开方函数结果永远精确建议写这种题目一律用它。4.4 模拟版和数学版怎么配合使用我的建议是练习阶段先把两个版本都写出来然后跑同一个n对比输出是否一致。如果一致说明你的模拟逻辑和数学推导都对上了如果不一致那一定是你某一个地方理解错了。这种“双轨验证”是调试程序很实用的手段。提交到OJ的时候追求稳妥和效率就直接交数学版。因为同样的数据模拟版可能用几百万次操作数学版只用几十次操作。虽然不是所有题目都能这样优化但只要你能找到数学规律就一定要用上。竞赛比的不是“能过”而是“稳稳地过”。5. 常见问题与调试经验这些坑我替你们踩过了5.1 数组越界与全局/局部变量最典型的错误是把数组开成door[n]然后循环里访问door[j]j最大是n其实越界了。C数组下标从0开始所以申请n个空间的下标范围是0到n-1。如果你打算从1开始编号就老老实实开door[n 1]宁可多开一个空间也不要越界。另一个容易出问题的是局部数组不初始化。你在main函数里写bool door[1005] {}; 这样会清零如果你只写bool door[1005]; 那里面就是随机值。全局变量虽然默认清零但并不是所有编译器在所有情况下都保证符合预期所以最安全的做法永远是显式初始化。5.2 循环边界与变量名混淆内层循环步长写错是另一个高频错误。比如把for (int j i; j n; j i)写成了for (int j 1; j n; j)原理没问题但慢很多更糟糕的是把外层循环变量i和内层循环变量j都写成i导致程序逻辑完全错乱。我建议所有人在写嵌套循环时变量名分开用i、j、k不要图省事复用同一个名字。这在任何语言里都是基本素养。真遇到了这种问题最快的排查方式是重新读一遍循环结构或者把n改小比如n5然后手动模拟一遍代码的执行过程看第一步、第二步是否和自己想的一致。5.3 输出格式导致的PE很多同学程序逻辑完全正确却因为输出格式不对被扣分。最常见的情况是数字之间多了一个空格比如先输出一个空格再输出数字最后行尾带着一个空格。有些OJ宽容一些但很多OJ会判Presentation Error。统一的做法就是用一个first变量标记第一个数。输出前判断if (!first) cout ; 然后再输出数字最后把first置为false。这样无论有多少个数字保证格式都是“数字 数字 数字”干净利落。5.4 i*i溢出用除法判断循环再强调一次判断“i的平方不超过n”时写i * i n在数据范围小的时候没问题但遇到n很大的时候i * i可能超过int类型的上限导致结果变成负数循环条件直接失效程序行为变得诡异。最稳妥的写法是i n / i。这个表达式的意思是除以i之后还大于等于i也就是i² ≤ n。它不用乘法就不会溢出。这个技巧在质数判断、素数筛、完全平方数判断里都经常用到是一个值得刻进肌肉记忆的细节。5.5 多组输入与隐藏要求一本通里这道题一般只有单组输入但有些学校和题库会把它改成多组测试比如输入一个n就输出一次答案直到文件结束。遇到这种情况C可以写成while (cin n)Python可以用while True加try。另外有些题目可能要求输出“开门的数量”而不是“哪些门开着”或者要求输出结果用换行而不是空格。这些都是在题目描述里容易忽略的小条件。我的习惯是提交前把题目描述再读一遍重点看输出格式那段别辛辛苦苦把算法写对了最后栽在格式上。下面整理一个快速排查表方便你对照检查症状可能原因解决方案程序运行时崩溃数组越界数组开大一点door[n 1]输出结果全部错误内层循环边界写错检查j的起点和步长样例过了但提交错没有处理多组输入改成while(cin n)输出之间没有空格忘了处理分隔符用first变量控制大整数测试异常i * i溢出改成i n / i局部数组值不确定未初始化显式清零或定义成全局数组6. 从开关门看竞赛思维变体与套路总结6.1 “状态翻转”类问题的通用解法开关门不是一道孤立的题目它代表着一个很常见的问题类型有一堆对象每个对象有“开/关”两种状态然后按某种规则反复翻转问最终状态。这类问题的通用解法可以总结成四步第一步把单点分析清楚一个对象的最终状态取决于它被翻转的次数的奇偶性。第二步数清楚这个对象被操作的条件是什么把它翻译成数学条件。比如本题中门k被第i个人翻转当且仅当i是k的约数。第三步把数学条件进一步化简找奇偶性规律。第四步只统计满足规律的对象而不要真的去模拟整个过程。这套思路的本质是“透过过程看终态”。很多竞赛题之所以难不是因为代码难写而是因为参与者太沉浸于“过程”本身忘了最终只关心“结果”。一旦掌握了这个思维遇到类似题目你就会条件反射地去找奇偶性和约数之间的关系。6.2 常见变体与实战改造先看一个最简单的变体如果人数不是n而是m且m n那么第m1到第n扇门完全不会被碰仍然是关的。而1到m号门的状态要看它们在1到m中的约数个数是奇是偶不能直接用完全平方数结论因为大于m的约数不会再有人去操作。这种题就只能老实模拟或者对每个门做一次约数计数。再看第二个变体把“翻转”改成“第i个人对编号为i的倍数的门做‘开变关关变开’”其实这就是原题。但如果改成“第i个人只操作编号为素数倍数的门”约数的概念就要换成质因数结论也会完全不同。第三种变体很常见只问最后开了几扇门。答案就是⌊√n⌋代码一行就够。别小看这个结论很多涉及约数个数奇偶性的题都会用它做铺垫。还有一个方向是“区间翻转”给一个长度为n的01数组做若干次区间取反问最终结果。这类题通常用差分或线段树思路也是计算每个位置被翻转了多少次再判断奇偶性。说到底核心还是我们今天讲的“奇偶性决定终态”。6.3 拿捏这题的三个思维习惯第一先手算后编码。尤其是n不大于20的样本花两分钟手推一遍你对题目的理解会深很多。代码写不出来往往不是不会码而是题意没吃透。第二看到“翻转”“开关”就条件反射地想奇偶性。奇数操作等于反转偶数操作等于没操作。这是所有状态翻转类问题的共同钥匙。第三约数成对出现是开关门问题的命门。你甚至可以把这个结论当套路记住但更重要的是会推导。因为题目只要稍微改一个条件结论就变了只有掌握推导过程你才能以不变应万变。这道题我陆陆续续带过好几届学生几乎每年都会发现有人卡在同一个地方不是不会写模拟而是写完之后不愿再多想一步。如果你现在正处于“能模拟但看不出数学规律”的阶段不用急这很正常很多人都是这样过来的。把n10手推一遍再拿笔写一写每扇门的约数你很快就会发现答案为什么总是平方数。这个发现过程本身比会做这一道题有价值得多。