在洛谷的讨论区或者新手群里“P1075是不是秒杀题”这个问题几乎每个赛季都会出现一次。我的回答通常很直接是但前提是你得真正想明白它为什么能被秒杀。很多人扫一眼题名“质因数分解”立刻开始默写分解质因数的万能模板枚举、除干净、存列表、取最大值样例倒是能过一提交到大数据的评测点就傻眼了。我自己第一次做这题也栽过当时写的还是从2枚举到n的暴力循环思路完全正确代码也没有任何bug但就是超时挂掉。后来我才想明白这道NOIP 2012普及组的题目核心考点根本不是“你会不会分解质因数”而是你能不能从题面给出的特殊结构里发现——只需要枚举到√n就够了。如果你正在用洛谷刷基础题或者第一次接触NOIP普及组的复杂度优化这篇文章就把整个思考链路拆开讲透题面里藏了什么条件、√n这个上界怎么推、代码怎么写才稳以及这题背后连着多大的一个世界。1. 题面里的隐藏条件这道题并不是让你“分解”所有因数先别急着写代码把题面一句话掰开揉碎“已知正整数n是两个不同的质数的乘积试求出较大的那个质数。”这句话和信息学竞赛里绝大部分“质因数分解”题都不一样它给了两个非常强的约束n恰好是两个质数相乘而且这两个质数还不相等。1.1 “两个不同质数”意味着n的因数表只有四个元素如果n p × q其中p和q都是质数并且约定p q那么n的全部正因数只有四个1、p、q、pq。为什么这背后是算术基本定理——每个大于1的整数都能唯一地分解成质因数的乘积。既然n的质因数分解就是“p乘q”那么任何能整除n的数它的质因数只能来自p和q这两个选择方式只有“出现或不出现”两种组合一下就是2×24种。这个结论看起来平平无奇但它直接指向了解法从2开始从小到大枚举第一个能整除n的整数一定就是那个较小的质数p。因为比p小的正整数尤其是指质数全都不可能是n的因数而p本身排在第一位。找到p之后较大的质数就是n ÷ p。整个过程不需要维护数组不需要保存所有因子一次除法直接输出答案。1.2 数据范围一个精心设计的“复杂度分界线”NOIP 2012普及组的原题里n上限我记得是2×10^9这个量级。这个数字选得非常有讲究——它恰好卡在int类型能装下的边缘int的上限约2.147×10^9所以用int存n不会溢出但也没有给你留多少余地。更有意思的是√(2×10^9)约等于44721四万多次循环对任何语言来说都是毫秒级的事情。也就是说出题人在用数据范围明确告诉你O(n)的算法我不打算让你过O(√n)的算法我闭着眼睛放行。如果你写的是for (int i 2; i n; i)最坏情况下要执行约20亿次取模运算。取模不是免费操作现代CPU每秒大概能跑10^8到10^9次简单整数运算而取模比加法、比较都慢20亿次铁定超时。但如果你把循环上界改成√n四万多次取模连热身都算不上。这道题的题名“质因数分解”其实是个误导它考的不是分解流程而是“你能不能根据n的结构把枚举范围缩小”。这种从题面条件出发推导算法上界的能力恰恰是普及组和提高组之间的一道分水岭。2. √n这个上界是怎么来的一个直观推导和三种边界写法既然答案是“枚举到√n”这个上界到底怎么来的一句话就能说明白对于任意整数n如果能写成n a × b并且假定a ≤ b那么一定有a² ≤ a × b n所以a ≤ √n。换句话说一对因子里面较小的那个不可能超过根号n。你只需要在[2, √n]里找找到了较小的因子a较大的因子b就直接用n ÷ a算出来。2.1 用实际数字走一遍感受循环什么时候停拿n 77举例。√77约等于8.77从2开始试2不行、3不行、4不行、5不行、6不行到7的时候77 ÷ 7 11整除成功。7是较小的质因子较大的就是11。循环到8就停了根本不需要去看9、10、11这些更大的数因为一旦在根号范围内找到因子成对的另一个因子必然大于根号。再试一个更极端的边界假设n接近2×10^9并且它的较小质因子非常接近√n比如p 44711。那么循环几乎要一直枚举到44711才命中看起来“很亏”但也就四万多次。这就是O(√n)的稳定性——无论输入多难缠循环次数都被牢牢限制在根号量级不会出现暴力枚举那种“数据好就秒过数据差就超时”的赌博心态。2.2 三种循环边界写法为什么我只推荐n / i写循环上界的时候新手最常见的三种写法效果完全不一样我按踩坑程度排个序i * i n最直观但有个隐患。ii在n很小的时候没事可一旦n放大到10^12甚至更高ii可能直接溢出int。P1075的n只有2×10^9i最大4万不会出问题但竞赛里养成的习惯会跟着你走很久最好从一开始就避开这种有隐患的写法。i sqrt(n)有人喜欢把sqrt(n)直接写在循环条件里每轮都调用一次sqrt函数浪费性能有人先算好int t sqrt(n)再用这又会引入浮点精度问题。举个例子n25时数学上sqrt(25)5但浮点运算可能得到4.999999int截断后就变成4循环上界少1直接漏掉真因子5。这不是理论上的风险是我真踩过的坑。i n / i这是我最推荐的写法。它本质上和i*in等价但用除法表达一来不会溢出二来没有浮点误差每轮只多一次整数除法性能损失可以忽略。P1075这种题根本不在乎多一次除法但“边界写法不出错”比“快一点点”重要得多。3. 三版代码逐行对比从TLE到AC的距离只有一行光说不练假把式直接上代码。这一节我从最暴力的版本开始一步步改到能稳过评测的版本顺便把比赛中那些没人写进题解的输入输出细节也讲掉。3.1 暴力版本思路对但复杂度扛不住#include cstdio int main() { int n; scanf(%d, n); for (int i 2; i n; i) { if (n % i 0) { printf(%d\n, n / i); break; } } return 0; }这段代码的问题不在逻辑而在最坏情况。如果n给到接近20亿并且较小的质因子在4万左右循环确实只需要4万次但如果n 2 × 999999937这种i2就命中了又是秒过。换句话说这个算法的时间完全取决于输入数据的“人品”最坏情况下要跑20亿次取模评测系统给它一个极限数据就原形毕露。竞赛算法讲究的是“最坏情况复杂度可控”这种看数据吃饭的写法在正式比赛里就是定时炸弹。3.2 根号枚举版本一行之差量级天壤之别#include cstdio int main() { int n; scanf(%d, n); for (int i 2; i n / i; i) { if (n % i 0) { printf(%d\n, n / i); break; } } return 0; }改动只有一行i n 变成了 i n / i。效果是整个循环次数从最多n次变成最多√n次。n2×10^9时暴力版本最多20亿次根号版本最多44721次两者差了四个数量级。找到第一个因子立即break也成立因为根据第1节的推理第一个因子必然就是较小的质数p直接输出n / p不需要任何额外处理。Python版本我也留一份很多初学者用Python刷洛谷import math n int(input()) for i in range(2, math.isqrt(n) 1): if n % i 0: print(n // i) break这里有个细节值得养成习惯我用的是math.isqrt而不是int(n ** 0.5)。isqrt从Python 3.8开始内置返回精确的整数平方根完全避开浮点误差。n2×10^9时int(n**0.5)大概率没事但如果你以后拿这段代码去处理更大的平方数附近的数据浮点取整可能让你漏掉边界因子到时候排查起来非常痛苦。3.3 输入输出和提交时的几个实际选择比赛里有个老生常谈的问题用cin还是scanfP1075只有一组输入一次输出cin和scanf的差距完全可以忽略。但如果你平时习惯cin/cout建议在main开头加上ios::sync_with_stdio(false); cin.tie(0);这能让C的流输入输出速度接近C标准库属于通用习惯。另外有人说这题可以特判偶数如果n是偶数且n2较小的质数必然是2答案就是n/2连循环都不用进。这话没错但实际写起来完全没有必要——因为循环从i2开始遇到偶数n时第一轮就命中了特判反而多写分支。老老实实写循环就好。4. “第一个找到的因子一定是较小的质数”——证明与通用分解模板上一节代码能AC靠的是一句“第一个因子必然就是p”。这句话为什么一定成立值得较真一下因为很多初学者在这里是含糊过去的。4.1 为什么第一个找到的因子不可能是合数有人会问从2开始枚举第一个整除n的i有没有可能是4、6、8这样的合数不可能。做一个反证假设某个合数d能整除n p × qd p。那么d的质因子也必然能整除n而且这些质因子都比d小当然也都比p小。可我们从2开始一路试到d-1这些质因子早就试过了全部不能整除n矛盾。更直接的说法是n的正因数只有1、p、q、pq四个。任何大于1且小于p的整数都不在这四个里面所以根本不可能整除n。因此第一次满足n % i 0的i只能是p不可能是其他东西。代码里的break是绝对安全的不会出现“先找到一个合数因子然后输出错误答案”的隐患。顺带一提题目特意强调“两个不同的质数”排除了n p²的情况。如果允许相等那么n49时pq7循环到7会命中输出7也正确处理逻辑其实不受影响。但“不同”这个条件让数论推导更干净也简化了数据构造。4.2 如果去掉“两个质数”的限制通用模板怎么写把题目升级一下不保证n是两个质数的乘积而是要求分解出任意的n的所有质因数。同样的根号枚举思路配合while循环把每个因子除干净就可以了int m n; for (int i 2; i m / i; i) { if (m % i 0) { while (m % i 0) { printf(%d , i); m / i; } } } if (m 1) printf(%d, m);注意两个细节。第一循环上界写的是m / i而不是n / i因为m在过程中会不断变小上界跟着缩小能减少无效枚举。第二每找到一个因子就用while把它从m里彻底除掉这样后续的合数i不会再整除m。举个例m12i2时把2除掉m变成3循环继续i3时m%30输出3m变成1。如果m10i2时输出2m变成5循环到i3时条件im/i也就是31不成立循环退出最后用if (m1)输出剩下的5。这个收尾处理非常重要它捕获了分解到最后残留的那个大质因子。P1075的本质其实就是这个通用模板在“恰好两个不同质数、指数都为1”时的特例不需要while循环不需要收集所有因子找到一个就立刻收工。理解了通用模板再回头看你就会发现那道题真的只是一层窗户纸。另外还可以提一个性能优化技巧枚举i时处理完2之后可以把步长改成2只试奇数循环次数直接减半。P1075用不上但你把通用模板搬到数据范围更大的题时这种小优化能救命。5. 从P1075看更大的世界质因数分解的应用与进阶一道普及组题目讲到这里其实已经到头了但这道题背后连接的话题非常值得展开。你可能觉得“分解两个质数的乘积”只是个竞赛玩具但它其实是现代密码学的一块基石。5.1 RSA加密与“乘法容易、分解难”的单向性RSA加密算法里有一个关键步骤选择两个大质数p和q计算n p × q。n会被公开作为公钥的一部分而p和q严格保密。为什么敢公开n因为从p、q计算n是一次乘法是瞬间的事但从n反推出p、q却难如登天。这就是密码学里的“单向函数”正向计算极快逆向计算极慢。用P1075的规模感受一下这个“慢”是怎么膨胀的。n≈2×10^9时试除法4万次就能分解n≈10^12时√n10^6还能轻松接受n≈10^18时√n10^9已经开始吃力n≈10^30时√n10^15普通计算机不可能完成。现代RSA常用的密钥长度是2048位n大约是2^2048 ≈ 10^617√n≈10^308这个数字比宇宙中的原子总数还要多得多。哪怕用地球上所有算力并行去试除算到宇宙毁灭也算不完。这就是为什么竞赛题会把数据范围卡在“根号枚举能过”的区间——因为一旦超过某个量级试除法就不再是“有点慢”而是“计算上不可行”。P1075那个2×10^9的上限等于是在告诉你这题只考你根号枚举考你理解到的边界就在这。5.2 数据再大怎么办Miller-Rabin与Pollard-Rho竞赛中的质因数分解题数据范围也会升级。当你遇到n在10^18左右的分解题时O(√n)的试除法循环10^9次C也扛不住。这时候通常的组合是Miller-Rabin做素性测试Pollard-Rho做因子搜索。Miller-Rabin基于费马小定理的推广能以极高的概率在O(k log n)时间内判断一个数是不是质数是“先判断再分解”的侦察兵。Pollard-Rho则利用生日悖论通过构造伪随机序列来碰撞因子期望时间复杂度只有O(n^(1/4))。对n≈10^18来说n^(1/4)约31623次比10^9次不知道快到哪里去了。这两个算法都是进阶内容但思维路径和P1075一脉相承先缩小范围再快速验证最后精准命中。P1075用到的√n枚举正是这条路径上最原始的一块砖。5.3 顺着这条线在洛谷上怎么继续练如果你在洛谷刷题做完P1075之后可以立刻做几个变形训练第一把题面改成“n是两个质数的乘积但允许相等”看看代码要不要改第二把数据范围脑补成10^12想想同样写法还能不能过第三去刷几道质数筛、区间质数统计的题你会发现“只枚举到√n”这个直觉反复出现。我个人建议别急着往上跳。很多人听说Pollard-Rho很酷上来就啃结果连Miller-Rabin的判定原理都没理清代码抄都抄不对。先用P1075把枚举上界、break时机、边界写法这些基本功焊死再去够进阶算法路会顺很多。最后分享一个我自己养成的小习惯拿到任何枚举题第一件事不是写循环而是先算数据范围对应的√n是多少。P1075是四万多次随便写某题n给到10^12√n是10^6试除法还能挣扎一下n一旦到10^18√n就是10^9直接换算法别跟它硬刚。这个“先估复杂度再动手”的习惯比背多少模板都有用。