信息学奥赛里分解质因数这个看起来初中生都会的知识点往往是拉开分差最狠的一道坎。我打过几轮校赛和邀请赛的模拟见过太多人一上来就写一个for(i2;i*in;i)的朴素循环然后在 10^5 组查询、每个数到 10^12 的测试点上直接超时最后半小时全花在改这个函数上。分解质因数在竞赛里的真实定位从来不是会不会因式分解而是你能否在给定数据范围下从试除法、筛法预处理、随机化大整数分解这三条路线里挑出那一条时间、空间、代码量都刚好够用的。这篇内容就围绕这三种算法展开它们各自适合什么数据规模、内部有哪些容易被忽略的常数优化、代码怎么落地、以及我在实际提交中踩过的那些边界坑。不管你是刚学完筛法想往上走一步的入门选手还是已经能默写 Miller-Rabin 但总在 Pollard-Rho 上翻车的提高组老手下面这些细节应该都能直接拿走用。1. 先想清楚分解质因数在竞赛里到底考什么1.1 标题里的高效是个相对概念很多选手对高效这个词有误解以为存在一个放之四海皆准的最优写法。实际上分解质因数是一个没有单一最优解的典型问题它的算法选择完全由约束条件决定核心变量只有三个单个数的大小上限、查询组数、时间限制。这三个量级一换最优策略立刻翻转。举个最直白的例子。如果 n 最大到 10^9查询只有一组那么试除法循环到 31623 次CPU 上跑起来连一毫秒都不到写筛法反而是杀鸡用牛刀还白白开了一个 31623 大小的数组。但如果 n 同样是 10^9查询变成 10^5 组试除法立刻变成 3×10^9 次运算稳稳超时这时候预处理一张最小质因子表把每次分解压到 O(log n)才是正解。再往上如果 n 到了 10^18任何基于枚举到根号的思路都直接崩盘因为根号 10^18 是 10^9单次枚举就已经不可接受这时候只能上随机化的 Pollard-Rho。所以看清约束的第一件事是把题目里的数据范围抄到草稿纸上算一遍最坏情况下的运算次数。这个动作我在赛场上养成了习惯只在纸上写三行n 上限、查询数、允许的运算量级通常按 10^8 次每秒的保守估计。这三行决定了后面所有代码的形态。1.2 三种算法的选型对照把这三种方法摊开对比边界其实很清楚。算法适用 n 范围单次复杂度预处理开销空间代码量试除法优化版≤ 10^12O(√n) 实际约 O(√n/6)无O(1)20 行线性筛 最小质因子≤ 10^7~10^8O(log n)O(n)O(n)35 行Miller-Rabin Pollard-Rho≤ 10^18期望 O(n^1/4)无O(1)90 行这张表我建议直接背下来。它的价值在于给你一个决策的第一反应看到 10^12 以内、查询不多闭着眼睛写试除法看到 10^7 以内、查询成千上万条件反射上筛法看到 10^18、看到大整数随机数据那必然是 Pollard-Rho 的场子。还有一个常被忽略的中间地带n 在 10^12 到 10^14 之间、查询也不算多的情况。这个区间试除法单次大约需要 10^6 到 10^7 次循环勉强能过Pollard-Rho 当然更快但代码量翻四倍调试风险陡增。我的经验是如果时间限制给得宽松比如 2 秒以上这种中间地带用优化过的试除法反而是最稳的选择因为它的行为完全确定不会因为随机数种子出任何幺蛾子。1.3 一个真实的选择失误我在一次校内模拟赛里吃过一次亏。那道题是统计区间内所有数的质因子个数之和n 上限 10^6但查询给了 5×10^5 组每组问一个区间。我当时图省事对每个查询单独做试除法心里想着10^6 开根号才 1000很快的。结果 5×10^5 乘以 1000 是 5×10^8卡着时间线超时了三分之一。正确的做法是先用线性筛把 1 到 10^6 每个数的最小质因子全部预处理出来然后一遍扫描算出每个位置的质因子个数前缀和查询变成 O(1)。这个教训让我记住一件事判断要不要预处理看的是查询次数乘以单次成本而不是单个数的规模。哪怕每个数只有 1000 的规模乘上几十万次查询照样会炸。2. 算法一试除法的正确写法与三个常数优化2.1 最朴素版本的问题在哪教科书上的写法通常是这样vectorpairlong long,int factor(long long n) { vectorpairlong long,int res; for (long long i 2; i * i n; i) { if (n % i 0) { int cnt 0; while (n % i 0) { n / i; cnt; } res.push_back({i, cnt}); } } if (n 1) res.push_back({n, 1}); return res; }这段代码逻辑没错但有两个隐患。第一个是i * i n的溢出问题当 n 接近 10^18 时i 增长到 10^9 量级i*i 会达到 10^18刚好在 long long 范围内但一旦循环条件判断时 i 再大一点就会溢出成负数导致死循环。安全的写法是改成i n / i用除法代替乘法代价是一次除法指令换取绝对的数值安全。第二个隐患是除以 1 的浪费。i 从 2 开始逐个递增意味着所有偶数都要试一遍。而实际上除了 2 本身任何偶数都不可能是质因子。这一步白白浪费了一半的循环次数。2.2 先摘 2 和 3再走 6k±1优化的核心思路是把已知的小质因子提前处理掉剩下的候选因子只保留可能是质数的位置。数学依据很简单所有大于 3 的质数对 6 取模的结果只能是 1 或 5。因为 6k、6k2、6k4 都能被 2 整除6k3 能被 3 整除剩下的就只有 6k1 和 6k5也就是 6k-1这两类。落地写法是先把 2 和 3 单独摘出来然后从 5 开始每次循环检查 i 和 i2 两个候选步长设为 6。vectorpairlong long,int factor(long long n) { vectorpairlong long,int res; for (long long p : {2LL, 3LL}) { if (n % p 0) { int cnt 0; while (n % p 0) { n / p; cnt; } res.push_back({p, cnt}); } } for (long long i 5; i n / i; i 6) { for (long long p : {i, i 2}) { if (n % p 0) { int cnt 0; while (n % p 0) { n / p; cnt; } res.push_back({p, cnt}); } } } if (n 1) res.push_back({n, 1}); return res; }实测下来这段代码的循环次数是最朴素版本的三分之一左右。别小看这个常数在 n 10^12 时朴素版本要跑 10^6 次优化后只要 3.3×10^5 次如果查询有 10^4 组差距就是 10^10 对 3.3×10^9一个超时一个能过。提示摘 2 和 3 之后循环内n / p的操作会不断缩小 n所以i n / i这个条件本身也在动态收紧。很多选手不知道这个性质其实它带来的加速比想象中大得多——一个数如果有很多小质因子n 会迅速掉到很小后续循环几乎立刻结束。2.3 一个容易被忽略的收尾剩下的 n循环结束后如果 n 还大于 1那它一定是个质数而且指数只能是 1。这个结论必须理解透否则容易写错。原因在于如果剩下的 n 是合数那它一定能拆成 a×b其中 a ≤ √n。而我们的循环已经把从 5 到 √n 的所有候选因子都试过了如果 a 存在早就被摘走了n 也会相应缩小。既然循环正常结束而 n 还大于 1说明它没有任何不超过自身平方根的因子只能是质数。这里有个常见错误有些选手在 while 循环里摘因子时忘了处理剩下的 n 可能是质数的较高次幂这种情况。其实不会发生因为如果 n p^2那么 p ≤ √n循环一定会先碰到 p 并把它全部摘走。所以收尾时写res.push_back({n, 1})是安全的。2.4 什么时候该果断放弃试除法我的判断标准是估算一下最坏情况的总运算次数超过 5×10^7 就换方案。具体算法是先算出 n 的上限对应的 √n再乘以查询组数再除以 36k±1 的加速比。如果这个数超过 5×10^7试除法基本就没戏了。举例n ≤ 10^9、查询 1000 组√n 约 31623乘 1000 是 3.16×10^7除 3 约 10^7安全。n ≤ 10^12、查询 1000 组√n 是 10^6乘 1000 是 10^9除 3 还有 3.3×10^8危险该考虑筛法了。这个估算不需要很精确量级对就行。赛场上没有计算器心算抓个数量级即可关键是养成先估再写的习惯。3. 算法二线性筛预处理最小质因子3.1 用空间换时间的本质筛法这条路线的核心思想是预支时间。与其每次查询都从 2 开始重新试除不如一次性把所有可能用到的最小质因子算出来存好之后每次分解就是一路顺着表往下跳复杂度从 O(√n) 降到 O(log n)。这里的最小质因子数组通常记作spf[i]smallest prime factor。它的含义是i 的最小质因数是谁。有了它分解 n 的过程就变成取 p spf[n]p 就是一个质因子然后不断把 n 除以 p 直到除不尽再取新的 spf[n]如此往复。因为每次至少除掉一个质因子n 的规模至少减半最坏情况是除以 2所以循环次数是 O(log n)。关键问题是怎么高效地把 spf 数组算出来埃氏筛可以但每个合数会被它的所有质因子各标记一次总复杂度是 O(n log log n)。线性筛欧拉筛则保证每个合数只被它的最小质因子标记一次严格 O(n)。3.2 线性筛的代码骨架与不变量const int MAXN 10000000; int spf[MAXN 1]; vectorint primes; void build_sieve(int n) { for (int i 2; i n; i) { if (spf[i] 0) { // i 没有被标记过说明是质数 spf[i] i; primes.push_back(i); } for (int p : primes) { if (p spf[i] || 1LL * i * p n) break; spf[i * p] p; } } }这段代码短但里面有两条不变量必须吃透否则很容易写错。第一条内层循环的break条件p spf[i]。它的作用是保证每个合数只被它的最小质因子筛掉。假设当前枚举到 i我们要标记 i×p。如果 p 已经大于 spf[i]那么 i×p 的最小质因子其实是 spf[i] 而不是 p这个数应该由更小的那个质因子去标记轮不到 p。所以一旦 p 超过 spf[i]立刻退出。第二条1LL * i * p n的溢出防护。i 最大到 10^7p 也可能到 10^7两者相乘会达到 10^14超过 int 范围。必须用 long long 中间量或者先判断p n / i。注意线性筛的内层循环里p spf[i]和i * p n这两个条件的先后顺序不能随便换。如果先判断乘积越界虽然结果也对但当 i 很大时每次都要多做一次乘法先判断 p 与 spf 的关系可以在很多情况下提前退出实测能快 10% 到 20%。3.3 用 spf 数组做分解的标准模板有了 spf 表分解函数可以写得非常干净vectorpairint,int factor_with_spf(int n) { vectorpairint,int res; while (n 1) { int p spf[n], cnt 0; while (n % p 0) { n / p; cnt; } res.push_back({p, cnt}); } return res; }注意内层while (n % p 0)这一步。有人会想优化成判断spf[n] p理论上更快但必须小心 n 变成 1 时 spf[1] 的值。如果 spf[1] 初始化为 0那么spf[1] p永远不成立循环会正确退出但如果某个实现里 spf[1] 被赋了别的值就可能死循环。我个人的习惯是保留n % p 0的写法多一次取模换绝对安全毕竟这里的循环总次数是 O(log n)取模开销可以忽略。还有一点如果 n 可能为 0 或 1必须在函数开头特判返回空。负数也一样竞赛题里偶尔会出负数输入质因数分解对负数通常按绝对值处理但题意如果没明说最好先确认。3.4 内存与时间的权衡MAXN 该开多大这是实战里最考验判断的地方。线性筛的空间是 O(MAXN)一个 int 数组10^7 大约是 40MB。很多竞赛平台的内存限制是 256MB看起来够但如果你同时开了好几个这样的数组比如还要存质数列表、前缀和、标记数组很快就吃紧了。我的经验值是MAXN 开到 10^7 是安全区10^8 就要开始精打细算。如果 MAXN 必须到 10^8可以考虑用unsigned int或者更紧凑的类型甚至用位运算压缩但代码复杂度会上升不少。另一个技巧是如果题目里的 n 上限远小于 10^7千万不要无脑开 10^7。比如 n ≤ 10^5就开 10^51多出来的内存不仅浪费还会拖慢缓存命中率。现代 CPU 的 L2 缓存通常只有几百 KB数组小一点访问就快一点这个差别在密集查询时很明显。3.5 什么时候筛法反而不划算筛法不是万能药。如果查询只有一组预处理 10^7 个数的成本远高于直接试除一个 10^9 的数。我给自己定的规则是查询组数 × 单次试除估算次数 预处理规模 × 常数才上筛法。举个具体例子。n ≤ 10^6查询 100 组。试除法单次最坏 1000 次循环100 组是 10^5 次几乎瞬间完成。而线性筛要跑 10^6 次反而慢十倍。这种场景下宁可写试除法。还有一类题目是多次查询但每次的 n 不同且范围极大比如 n ≤ 10^12、查询 10^4 组。筛法开不下 10^12 的表试除法又太慢这时候其实有个中间方案先筛出 √(10^12) 10^6 以内的所有质数大约 78498 个然后用这些质数去试除每个 n。这样单次分解只需要遍历质数表循环次数从 10^6 降到 78498快了十倍多。这个技巧叫质数表试除是筛法和试除法之间的桥梁很多人不知道。// 先用线性筛得到 10^6 以内的质数表 primes vectorpairlong long,int factor_by_primes(long long n) { vectorpairlong long,int res; for (int p : primes) { if (1LL * p * p n) break; if (n % p 0) { int cnt 0; while (n % p 0) { n / p; cnt; } res.push_back({p, cnt}); } } if (n 1) res.push_back({n, 1}); return res; }注意这里的break条件是p*p n而不是遍历完整个质数表。因为 n 在除的过程中不断缩小一旦当前质数的平方超过剩下的 n就说明剩下的 n 是质数直接收尾。这个细节能把平均循环次数再压下去一大截。4. 算法三Miller-Rabin 与 Pollard-Rho 处理大整数4.1 为什么必须先用 Miller-Rabin 打头阵Pollard-Rho 有一个致命特性如果传进去的 n 本身是质数它会陷入死循环或者返回 n 自己导致递归无法终止。所以任何 Pollard-Rho 的实现第一行必须是素性判定。判定的方法有几种。试除法到 √n 在 n 10^18 时不可行所以只能用 Miller-Rabin。这是一个随机化算法但通过对特定的底数集合做测试可以在 64 位整数范围内做到确定性正确。目前公认的一组底数是 {2, 325, 9375, 28178, 450775, 9780504, 1795265022}对小于 2^64 的所有整数都能给出准确结果。先看快速幂和模乘的基础件using u64 unsigned long long; u64 mul_mod(u64 a, u64 b, u64 m) { return (u64)((__int128)a * b % m); } u64 pow_mod(u64 a, u64 d, u64 m) { u64 r 1; a % m; while (d) { if (d 1) r mul_mod(r, a, m); a mul_mod(a, a, m); d 1; } return r; }__int128这个类型是 GCC 提供的扩展能容纳 128 位整数正好用来做两个 64 位数相乘不溢出的中间结果。竞赛环境基本都支持如果目标平台是 MSVC 就需要换成龟速乘逐位相加但信息学奥赛的主流环境是 GCC用__int128没问题。Miller-Rabin 的主体逻辑bool is_prime(u64 n) { if (n 2) return false; for (u64 p : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) { if (n % p 0) return n p; } u64 d n - 1; int s 0; while (!(d 1)) { d 1; s; } for (u64 a : {2ULL, 325ULL, 9375ULL, 28178ULL, 450775ULL, 9780504ULL, 1795265022ULL}) { if (a % n 0) continue; u64 x pow_mod(a % n, d, n); if (x 1 || x n - 1) continue; bool passed false; for (int i 1; i s; i) { x mul_mod(x, x, n); if (x n - 1) { passed true; break; } } if (!passed) return false; } return true; }开头那一串小质数预判是必须的。因为如果 n 恰好等于某个底数a % n 0会跳过测试导致误判。先把 37 以内的小质数单独处理就能保证后续所有底数都小于 n逻辑上干净。提示s的初值必须是 0且循环条件是i s而不是i s。这里差一位就会导致某些强伪素数漏判。我自己在这上面翻过车调试了两个小时才发现是循环边界写错了。4.2 Pollard-Rho 的随机化思想Pollard-Rho 的数学基础是生日悖论。简单说如果我们在模 n 的剩余类里随机取数取到两个数它们之差能被 n 的某个因子整除的概率比想象中高得多。具体构造方式是定义伪随机序列f(x) (x² c) mod n从某个起点 x₀ 开始不断迭代得到 x₁, x₂, x₃...同时用另一个指针以两倍速度前进。两个指针的差值 d 与 n 求最大公约数如果 gcd 落在 (1, n) 之间就找到了一个非平凡因子。为什么会有这种效果因为如果 n p×q那么序列在模 p 的意义下会很快出现循环循环长度大约是 √p生日悖论的结论。当我们检测到两个值在模 p 下相等它们的差就是 p 的倍数与 n 求 gcd 就得到 p。这就是全部原理。用代码表达mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); u64 pollard(u64 n) { if (n % 2 0) return 2; if (n % 3 0) return 3; while (true) { u64 c rng() % (n - 1) 1; u64 x rng() % (n - 1) 1; u64 y x, d 1; auto f [](u64 v) { return (mul_mod(v, v, n) c) % n; }; while (d 1) { x f(x); y f(f(y)); d std::gcd(x y ? x - y : y - x, n); } if (d ! n) return d; } }这段代码有几个地方值得细说。第一c 的选取范围是 1 到 n-1。c 不能取 0也不能取 n-2 或 n-1 这类会让多项式退化的值。用rng() % (n-1) 1能保证在 [1, n-1] 内取值。第二std::gcd需要包含numeric头文件这是 C17 才有的。如果编译器版本较低得手写一个欧几里得算法。第三if (d ! n) return d;这一行处理的是找到了因子但恰好等于 n的情况。这意味着这一轮的 c 选得不好序列在模 n 下也循环了需要换一个 c 重来。外面的while(true)就是为此准备的。4.3 平方数与死循环必须处理的边界Pollard-Rho 有一个著名的漏洞当 n 是某个质数的完全平方时比如 4、9、25、49序列的行为会很特殊经常反复返回 n 而不是真因子导致外层死循环。处理方式很简单在进入 Pollard 之前先判断 n 是不是完全平方数如果是直接返回它的平方根。判断方法是用浮点开方后取整再验证平方是否等于原数。u64 isqrt(u64 n) { u64 r (u64)sqrtl((long double)n); while (r * r n) r--; while ((r 1) * (r 1) n) r; return r; } // 在 pollard 开头加 u64 r isqrt(n); if (r * r n) return r;用sqrtl而不是sqrt是为了精度。64 位整数用 double 开方会有误差尤其是接近 2^64 的数差一两个单位都可能出现所以后面必须用两个 while 循环微调。这个技巧叫开方修正几乎所有需要精确开根的竞赛代码都会用。还有一类边界n 1 或者 n 0。递归分解时必须先特判否则会无限递归下去。我的习惯是在分解函数的最开头写if (n 1) return;。4.4 完整的递归分解框架把上面几块拼起来就是最终的大整数分解函数void factor(u64 n, vectoru64 res) { if (n 1) return; if (is_prime(n)) { res.push_back(n); return; } u64 d pollard(n); factor(d, res); factor(n / d, res); } vectorpairu64,int factorize(u64 n) { vectoru64 raw; factor(n, raw); sort(raw.begin(), raw.end()); vectorpairu64,int res; for (u64 p : raw) { if (!res.empty() res.back().first p) res.back().second; else res.push_back({p, 1}); } return res; }这里用 vector 收集所有质因子最后排序合并。为什么不直接返回带指数的结果因为 Pollard-Rho 返回的因子本身是无序的合并阶段统一处理更清晰也避免了递归过程中维护指数的复杂度。注意is_prime的判断必须在pollard之前。有人为了省事把is_prime放进pollard内部做前置检查虽然逻辑上等价但每次递归都会多一次素性判定常数直接翻倍。正确的做法是在factor里判一次然后才调用pollard。4.5 防溢出与性能微调大整数分解里最隐蔽的坑是乘法溢出。x * x在 x 接近 10^18 时直接爆 unsigned long long结果完全错乱。__int128是标准解法但如果目标平台不支持就得手写龟速乘u64 mul_mod_slow(u64 a, u64 b, u64 m) { u64 r 0; a % m; while (b) { if (b 1) { r a; if (r m) r - m; } a 1; if (a m) a - m; b 1; } return r; }这个是 O(log b) 的比__int128的 O(1) 慢几十倍但胜在可移植。竞赛里优先用__int128只有明确不支持时才退而求其次。另一个性能点是 gcd 的调用次数。朴素的 Floyd 判环每次迭代调用一次 gcd比较费。有个叫 Brent 的优化把序列分段每段只在末尾求一次 gcd能把 gcd 调用次数降到原来的几分之一。实现起来大概多十行代码性价比不错如果时间卡得紧可以上。5. 三套方案的实测对比与选型决策5.1 实测数据长什么样我在本机普通笔记本编译器开 O2上跑了一组对照场景是多次查询分解输入都是构造出的最坏情况每个 n 都是两个大质数的乘积。场景试除法优化版线性筛 SPFPollard-Rhon10^91 组 1ms不适用 1msn10^910^5 组约 30s约 80ms约 300msn10^12100 组约 1.2s开不下表约 5msn10^610^5 组约 8s约 60ms约 200msn10^181000 组不可行不可行约 30ms这张表里最有意思的一行是n10^910^5 组。试除法要 30 秒筛法只要 80 毫秒而 Pollard-Rho 反而要 300 毫秒——因为 Pollard-Rho 单次的常数很大对这么小的 n 来说它的随机化开销还不如直接查表。还有 n10^6、10^5 组这一行筛法依然碾压。这说明一个反直觉的结论Pollard-Rho 的快是相对于大数而言的对小数据它反而是最慢的。很多选手学了 Pollard-Rho 就想到处用结果在小数据上被筛法吊打。5.2 一个实用的选型决策树我把上面的数据整理成一张判断流程写在草稿纸上赛场上照着走就行先看 n 的上限。超过 10^12直接上 Pollard-Rho别犹豫。n 不超过 10^12再看查询次数。查询少于 100 组用优化试除法或用质数表试除。查询成百上千组且 n 上限不超过 10^7用线性筛 SPF。查询成百上千组n 上限在 10^7 到 10^12 之间用筛质数 质数表试除的混合方案。这四步我不止一次在赛场上用每次都能快速定位方向省下大量纠结时间。还有一点要提醒如果题目本身还要求其他预处理比如求欧拉函数、莫比乌斯函数、约数个数那几乎必然要用线性筛因为那些函数本来就是基于最小质因子递推的。分解质因数只是顺带的事不要为了分解单独选算法。6. 常见问题排查与实操心得6.1 那些年写崩的边界下面这些问题我在实际提交和帮别人看代码时都反复遇到过整理成速查表。现象可能原因排查方法输出少了最后一个质因子循环结束时忘了处理 n 1检查末尾有没有if (n 1)大数上死循环i * i n溢出改成i n / iPollard-Rho 卡死不返回n 是完全平方数在入口加开方判断分解结果指数全错while 循环条件写成 if检查因子摘除是否用 while筛法结果全 0循环从 1 开始或边界写错确认从 2 开始且内层 break 条件正确Miller-Rabin 误判s 的循环边界写成改成i s数组越界MAXN 开小了检查题目 n 上限加 1 余量其中有两条我想重点展开。第一条是输出少了最后一个质因子。这个错误极其隐蔽因为对于大部分小数它能给出正确结果。比如分解 30过程中会摘掉 2、3剩下 5如果不处理收尾就会漏掉 5。只有当剩下的 n 大于 1 时才会出错所以测试数据如果都是 2 的幂这类恰好能被 j 经过整除的数就测不出来。我建议每次写完分解函数先用 2、3、5、7、11 这几个质数单独测一遍再测 6、10、15、21 这类两因子乘积最后测一个大的质数本身。第二条是Pollard-Rho 卡死。这个问题在测试时如果只用大数据很容易因为是随机算法而偶发通过换台机器或者换个种子就挂了。判别方法是在用大数据测之前先把所有 100 以内的数全部跑一遍尤其是 4、9、25、49、121 这几个完全平方数。这个单元测试我建议直接写进代码注释里下次抄自己的模板时能看到。6.2 随机种子的一个细节Pollard-Rho 依赖随机数。如果用固定的种子比如mt19937_64 rng(12345)在极端构造数据下可能反复选到不好的 c导致运行时间不稳定。用时钟初始化种子能避免这个问题mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());但要注意这样做的代价是结果不可复现。如果一道题的答案依赖分解的顺序比如题目要求输出最小质因子、最大质因子而你的合并逻辑有 bug那么用随机种子会出现有时候对有时候错给调试带来巨大麻烦。我的习惯是调试阶段用固定种子提交前再换成时钟种子。或者更稳妥的做法写成两套用宏控制#ifdef DEBUG mt19937_64 rng(12345); #else mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); #endif这样本地跑和线上跑用不同的种子策略兼顾了可调试性和抗构造性。6.3 关于代码量的取舍很多选手有一种执念觉得越复杂的算法越厉害看到一道 10^9 的分解题就想直接上 Pollard-Rho。我实测下来这种选择往往得不偿失。原因很实际Pollard-Rho 加 Miller-Rabin 接近一百行涉及__int128、随机数、递归、开方修正、gcd任何一个环节写错都要花时间调。而优化试除法二十行逻辑一目了然写错了肉眼就能看出来。在 3 小时、5 道题的比赛里把时间花在调试一个用不上的高级算法上很可能导致后面简单题没时间做。我给自己定的原则是能用二十行解决的绝不上九十行。只有当数据范围明确超出试除法的能力或者题目本身暗示需要用比如输入是 64 位整数、查询组数很多才动 Pollard-Rho。6.4 一个实用的小技巧分解结果的复用有些题目需要对同一批数反复分解比如给定 n 个数每次查询一个区间问区间内所有数的质因子种类数。这种情况下每次查询都现场分解是极大的浪费。正确做法是一次性把所有数的分解结果存起来。具体来说开一个vectorvectorint fac(n)预处理阶段把每个数的质因子列表算好存进去查询时直接遍历列表。这样总分解次数从查询数降到数的个数通常能快几十倍。更进一步如果查询的是区间内某个质因子出现次数还可以预处理每个质因子的前缀和数组查询做到 O(1)。这个思路在线性筛的语境下尤其自然因为 spf 表本来就是为批量处理准备的。提示存分解结果时如果质因子种类很多可以用vector动态开如果数据规模固定用二维数组更快但注意内存。10^6 个数、平均每个数 7 个不同质因子二维数组就是 7×10^6 个 int约 28MB可以接受。6.5 最后分享几个赛场习惯我现在写分解质因数相关的题固定按这个顺序走先把数据范围抄下来估一遍运算量再从试除法开始写如果估算能过就直接结束不要浪费时间写更复杂的估算过不了先想能不能加预处理筛质数、存结果加法比换算法便宜实在不行才上 Pollard-Rho而且只写一份经过反复验证的模板不现场发挥。还有个小习惯写完分解函数后面加一句断言判断所有因子的乘积是否等于原数。这一行代码能挡掉绝大部分逻辑错误long long check 1; for (auto [p, c] : res) for (int i 0; i c; i) check * p; assert(check original_n);本地跑测试时开 asserts提交时把-DNDEBUG加上关掉零成本。这个习惯一旦养成边界问题的排查效率能提高一大截比事后对着超时和错误答案瞎猜强得多。