1. 题目理解这道“进阶题”到底在考什么如果你刷过东华OJ的进阶题大概率会遇到这道“分解质因数”。题号排在第10位名字不花哨但很多人在它上面卡过。我第一次做的时候也觉得简单无非就是把一个数拆成质数相乘后来才发现“拆完”和“拆对”是两码事尤其面对多组输入、输出格式、边界数据时稍微大意一点就是WA。1.1 质因数分解的数学基础质因数分解其实是一个非常经典的数论概念任何一个大于1的正整数都能唯一地表示成若干个质数的乘积而且不考虑顺序时写法唯一。例如12 2 × 2 × 360 2 × 2 × 3 × 5100 2 × 2 × 5 × 5这个结论叫“算术基本定理”也是唯一分解定理。它听起来像废话但几乎所有关于整除、约数、最大公约数的问题最后都能追回到质因数分解上去。拿这道题来说它不要求你证明定理而是要求你切实地“把一个数拆干净”。很多同学一看到“质因数”三个字第一反应是先去写一个判断质数的函数然后再去遍历所有数字判断哪些是质因数。这样做不是不行但绕了很大的弯路。分解质因数的关键不在于“判断质数”而在于“吃掉因子”每找到一个能整除当前n的数i就要把n里所有的i全部除掉然后继续处理剩下的部分。这才是算法上的核心思路。1.2 东华OJ这道题究竟要求什么东华OJ的输入一般是一个正整数n输出要求形如1222377也就是等号左边是原数右边是它的质因数乘积因子从小到大排列乘号用英文星号*表示。题目如果要求“按从小到大的顺序”实际就是在告诉你质因数不能乱排必须严格递增或按重复次数排列。比如60必须输出602*2*3*5不能输出603*5*2*2。这个输出格式是一个典型的OJ隐藏考点。很多人算法写对了但因为等号后面没换行、乘号前多了一个空格、最后一个因子后面多打了一个*照样拿不到分。所以处理这道题时除了要会算还要把输出格式当成核心需求一样认真对待。1.3 “进阶”两个字体现在哪里如果仅仅是判断质数很多同学在刚学循环时就会了。但“分解质因数”把好几样东西放在了一起循环嵌套、数论基础、边界处理、输出格式控制、多组数据处理。而且它还是后续很多题目约数个数、约数和、欧拉函数、同余问题的基础组件。比如你现在学会了分解质因数后面遇到“求n有多少个约数”的题就能直接用分解结果来计算。也就是说这道题表面上只是刷题列表里的一小题实际上是在帮你建立一个数学转换工具。理解了这一点你就明白为什么OJ要把它放进进阶题里而不是放在最基础的“求质数”题目里。2. 算法设计为什么试除法够用以及一定要除到√n2.1 最直观的试除法模拟手算过程不考虑任何优化最本能的写法是从2开始从小到大依次枚举可能的除数i只要n能被i整除就输出一个i并把n除以i然后继续用i去试直到n不再能被i整除再把i加1。举个例子n60时这个过程是这样的60能被2整除输出2n变成3030还能被2整除输出2n变成1515不能被2整除i变成315能被3整除输出3n变成55不能被3整除i变成4不行i变成55能被5整除输出5n变成1结束。结果就是602*2*3*5。这个算法非常符合人的手算直觉代码写出来也很短。它的正确性依赖一个事实任何合数n至少有一个小于等于√n的质因子所以只要从小到大试就一定能先找到最小质因子再递归地处理剩余部分。2.2 为什么只需要试到√n这是这道题最重要的优化点。如果n有一个大于√n的因子a那么它的配对因子b n/a一定小于√n。换句话说因子是成对出现的比如24的因子对是(1,24)、(2,12)、(3,8)、(4,6)左边一个不超过√24≈4.9。所以在试除过程中如果从2一直试到√n都没有找到能整除n的数那么n本身就是质数不需要再继续试下去了。最典型的例子是n17√17≈4.12试2、3、4都不能整除这时就可以直接断定17是质数。如果傻乎乎地从2试到16等于白白多算了三倍以上的循环次数。在代码里循环条件一般写成i n / i或者i * i n。注意这里不要写成i n否则一方面效率低另一方面也违背了“因子成对”的数学性质。2.3 循环条件里的n是“动态”的这里藏着一个非常经典的坑。很多人会把循环上界提前算好写成像这样int limit sqrt(n); for (int i 2; i limit; i) { ... }这种写法在少数情况下能碰巧过但逻辑上是不严谨的。因为在分解过程中n会不断变小每次除完一个因子后新的n对应的√n也会变小。比如n100一开始上限是10但当你把质因数2提出来之后n变成了25这时候理论上只需要试到5就够了没必要继续试到10。虽然多试几次结果不一定出错但会让算法变得冗余甚至在某些特殊数据下出现漏判或多余操作。正确的做法是让循环条件实时依赖当前的n也就是写成for (int i 2; i n / i; ) { ... }这样每循环一次都会用最新的n去判断是否继续。虽然代码只差了一点点但背后的数学思想完全不一样你是在和不断缩小的“待分解数”打交道而不是盯着一个固定不变的原始数字不放。2.4 先处理2的小优化循环次数直接减半在所有质数中2是唯一一个偶数。所以可以先把n中所有的因子2全部提取出来然后从3开始每次让i加2跳过所有偶数。这样一来循环次数大约减少一半。比如输入1000003如果从2一路试到1000002要吃不少时间而加上√n限制后最多只需要试到1000左右再跳过偶数实际循环只有500次左右几乎瞬间完成。虽然东华OJ这道题的n范围不一定那么大但这种优化思路非常值得养成。你可以把它理解为“把已知的常识变成代码里的条件”2以外的偶数都不可能是质数就不用浪费时间去做除法了。这段优化不是必须的但它能让你从“能过题”走向“会优化”。在刷OJ的过程中很多题目考的就是这种“比别人多想一步”的能力。3. C实现从零开始写一份能AC的代码3.1 函数怎么设计直接打印还是返回结果这道题本质上只要求输出所以最自然的做法是写一个void函数在函数内部完成分解和打印。但如果你想为后续的题目积累工具也可以设计成返回vectorpairint, int其中每个pair表示“质因子i出现了多少次”。我个人建议先从直接打印的版本开始把逻辑跑通后再扩展成通用版本。把分解逻辑单独抽出来还有一个好处main函数会非常干净只负责读取输入和调用函数。当OJ要求多组数据输入时这个结构能让你少犯很多低级错误。3.2 一份可以直接提交的C代码下面这份代码是我实际在东华OJ上测试过的写法没有用到任何花哨的库函数完全依赖循环和除法。#include iostream using namespace std; void decompose(int n) { if (n 1) { cout 11 endl; return; } cout n ; bool first true; for (int i 2; i n / i; ) { if (n % i 0) { if (!first) { cout *; } cout i; first false; n / i; } else { i; } } if (n 1) { if (!first) { cout *; } cout n; } cout endl; } int main() { int n; while (cin n) { decompose(n); } return 0; }代码核心分成三步。第一步处理n1的特殊情况因为1没有质因数但题目如果输入1你至少要输出11才符合等号两边相等的语义。第二步从小到大枚举i只要i能整除n就输出一个i并把n缩小直到不能整除为止。第三步循环结束后如果n仍然大于1说明它是一个还没来得及输出的质因子直接追加到末尾就行。3.3 为什么写i n / i而不是i * i n这是一个很多新手都会踩的坑。i * i n在数学上完全正确但在C里存在整数溢出风险。当n接近int上限2147483647时i只要超过46340i * i就会超出int能表示的范围变成负数循环判断直接失效。换成i n / i可以完美避开溢出因为除法不会超过int的范围。这种写法在竞赛里非常常见它不依赖64位类型也能保证安全。如果你实在喜欢i * i的写法至少写成1LL * i * i n用long long临时运算但说实话不如n / i干净。3.4 输出格式的几个经典坑等号左边是原数右边是分解式中间不要加空格除非题目明确要求。乘号是英文星号*不是字母x也不是中文乘号。第一个因子前不能输出*最后一个因子后也不能输出*。每行结束要换行多组输入时每组输出占一行。我用一个bool first标记来解决第一个因子的问题。初始为true第一次输出因子时不打印乘号随后把first改成false之后每次输出因子前都先打印一个*。这个技巧在输出逗号分隔、空格分隔时同样适用属于竞赛基础技能。3.5 如果题目要求输出指数形式有些变体题会要求把输出写成602^2*3*5也就是相同质因子合并成指数形式。这种改动也很容易实现核心是把“每找到一个因子立刻输出”改成“先数一下相同因子出现了几次再一次输出”。void decomposeExp(int n) { if (n 1) { cout 11 endl; return; } cout n ; bool first true; for (int i 2; i n / i; i) { if (n % i 0) { int cnt 0; while (n % i 0) { n / i; cnt; } if (!first) { cout *; } if (cnt 1) { cout i; } else { cout i ^ cnt; } first false; } } if (n 1) { if (!first) { cout *; } cout n; } cout endl; }这段代码体现了一个很重要的解题思路先处理共性逻辑再根据具体要求调整输出格式。算法本身的骨架没有变变的只是“如何表达结果”。这也是为什么我说分解质因数是个基础能力而不是一道孤立的小题。4. 调试、测试与常见问题4.1 用边界数据自测比跑十个随机数都有用很多人在本地测试时只跑题目给的样例样例过了就直接交结果WA。分解质因数这道题我建议你至少测下面这一组边界数据。输入期望输出说明111特殊边界最容易忘222最小的质数不能输出22*1442*2平方数检验循环边界有没有漏88222同一个因子出现多次1212223普通合数100100225*5多个不同因子且重复999983999983999983一个典型的大质数专门考验试除到√n的优化尤其是最后一项如果一个数本身是质数优化版本只试到约1000就能结束而暴力写法可能要循环到99万次。这组数据一测就能明显感受到算法优化的威力。4.2 最容易犯的三个错误第一个错误是忘掉在while循环里把n缩小。比如写成if (n % i 0) { cout i; }内存循环没有n / i结果就是同一个因子被无限打印程序卡死。记住每找到一个因子就必须把n“吃掉”一部分让问题规模变小。第二个错误是把循环条件写成i * i n少了一个等号。比如n4时i2时i * i恰好等于4如果用判断循环直接不进去最后输出44答案错误。这个等号问题非常隐蔽样例一般测不出来。第三个错误是输出顺序不对。比如先把*打印出来再判断是不是第一个因子结果第一项前面多了一个星号。这种格式错误在OJ判定里就是WA不会因为“算法对”就放过你。4.3 从“能过样例”到“能AC”自测清单除了跑上面的表格我还会做一个更稳妥的测试用暴力法做对照。写一个最简单的分解函数从2一直试到n虽然慢但绝对正确然后随机生成大量小数字让优化版本和暴力版本的结果逐一对比。这个方法虽然土但能抓出90%的隐藏bug。对于这道题你还可以刻意测试所有小于等于100的正整数把它们的输出结果全部打出来人工瞄一眼格式。我当年就是这么干的虽然看起来很笨但确实帮我发现了n1时没有输出的严重问题。4.4 OJ常见报错排查速查表报错类型常见原因Compile Error头文件缺失、变量名和关键字冲突、中文字符混入代码Wrong Answer输出格式不对、边界没处理、乘号写错Time Limit Exceeded循环到n而不是√n、每次循环都重复计算sqrtRuntime Error递归写法栈溢出、数组越界、除数为0如果出现Time Limit Exceeded先检查是不是把i n / i写成了i n。如果出现Wrong Answer优先检查输出里的等号、乘号、换行。如果这两项都没问题再检查n1和质数输入。4.5 多组输入和换行的处理东华OJ这类在线判题系统经常把多条测试数据放在同一个输入文件里要求程序全部处理完。最稳妥的做法就是用while (cin n)来读读到文件末尾自动结束。千万不要只读一次n就跑否则只有第一组数据能过。使用cin的好处还在于它会自动跳过空白字符包括空格、换行和Tab。你不需要手动处理\n带来的残留问题代码会干净很多。如果用scanf也要注意格式字符串的写法避免漏掉换行符。5. 从这道题延伸出去的几个方向5.1 质因数分解是很多数论题的前置技能学完分解质因数之后你会发现好多题都能从这里接到线。比如说一个数的约数个数可以通过它的质因数分解直接算出来。n p1^a1 * p2^a2 * ... * pk^ak那它的约数个数就是(a11)(a21)...(ak1)。举个例子60 2^2 * 3^1 * 5^1约数个数就是(21)(11)(11)12正好对应1、2、3、4、5、6、10、12、15、20、30、60这12个约数。约数和、最大公约数、最小公倍数、欧拉函数等概念也都能从质因数分解的角度重新理解。所以你现在写的这几十行代码未来会被反复利用。这也是我强烈建议你把它封装成函数的原因——以后遇到新题直接复制过去改改就行。5.2 递归写法另一种理解方式分解质因数还可以用递归来实现。思路是找到n的最小质因子i后输出i然后递归分解n/i。终止条件是n变成1或者n本身是质数时直接输出它。递归版本代码更短但需要注意输出格式而且对于int范围内的n来说递归深度完全够用不用担心栈溢出。不过我个人在OJ上更推荐迭代写法。递归虽然代码优雅但每次递归都会产生函数调用开销而且格式控制容易出错。在学习递归时你可以拿这道题来练手但在追求稳定AC的阶段迭代是更可靠的选择。5.3 多次查询时用质数表加速如果题目升级成“输入T组n每组输出质因数分解”你再对每个n都从2开始试除就会重复做很多无用功。更好的做法是先用埃氏筛把[2, √maxN]范围内的所有质数一次性筛出来然后只拿这些质数去试除n。这样既可以跳过所有合数又能处理大量查询。埃氏筛的核心思想很简单从2开始把每个质数的倍数全部标记为合数。代码大概长这样vectorbool isPrime(maxN 1, true); isPrime[0] isPrime[1] false; for (int i 2; i * i maxN; i) { if (isPrime[i]) { for (int j i * i; j maxN; j i) { isPrime[j] false; } } }筛完之后把isPrime里为true的下标收集到一个vectorint primes里分解时只遍历这个质数表。这个优化思路在东华OJ的进阶题和更高难度的算法题里非常常见属于从“会分解一个数”到“会处理一批数”的关键一步。5.4 如果n非常非常大呢当n达到10^18级别时试除法就不够用了需要借助Pollard-Rho算法和Miller-Rabin素性测试。这些算法属于竞赛进阶内容东华OJ的基础题大概率不会涉及。但理解它们存在的原因是必要的——算法复杂度决定了你能处理的数据范围。试除法是O(√n)Pollard-Rho的期望复杂度则快得多。先掌握好试除法和筛法再一步步往上走这样知识体系才稳固。5.5 一个小技巧先让思路跑通再写代码最后分享一个我自己的做题习惯。拿到这种“看起来很简单”的题先不要急着打开编辑器敲代码而是拿纸笔把n60的分解过程写一遍看自己手算是怎么做的代码就照着那个过程写。我写分解质因数时脑子里始终记着一句话找到一个质因子后就把它从n里除掉直到除不动为止。只要这句话没忘循环条件、n的更新、最后的质数输出都能顺理成章地写对。如果你现在正卡在东华OJ这道题上建议按这个顺序排查先跑n1、n4、n质数这三组数据再看输出里的等号和乘号最后确认循环上界用的是不是n/i。这三关过了这道题基本就稳了。