信息学奥赛里，分解质因数这个看起来"初中生都会"的知识点，往往是拉开分差最狠的一道坎。我打过几轮校赛和邀请赛的模拟，见过太多人一上来就写一个for(i=2;i*i<=n;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 三种算法的选型对照

把这三种方法摊开对比，边界其实很清楚。

这张表我建议直接背下来。它的价值在于给你一个决策的第一反应：看到 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 最朴素版本的问题在哪

教科书上的写法通常是这样：

vector<pair<long long,int>> factor(long long n) { vector<pair<long 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、6k+2、6k+4 都能被 2 整除，6k+3 能被 3 整除，剩下的就只有 6k+1 和 6k+5（也就是 6k-1）这两类。

落地写法是：先把 2 和 3 单独摘出来，然后从 5 开始，每次循环检查 i 和 i+2 两个候选，步长设为 6。

vector<pair<long long,int>> factor(long long n) { vector<pair<long 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，再乘以查询组数，再除以 3（6k±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]; vector<int> 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^7，p 也可能到 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 表，分解函数可以写得非常干净：

vector<pair<int,int>> factor_with_spf(int n) { vector<pair<int,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^5+1，多出来的内存不仅浪费，还会拖慢缓存命中率。现代 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 vector<pair<long long,int>> factor_by_primes(long long n) { vector<pair<long 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>头文件，这是 C++17 才有的。如果编译器版本较低，得手写一个欧几里得算法。

第三，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, vector<u64>& 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); } vector<pair<u64,int>> factorize(u64 n) { vector<u64> raw; factor(n, raw); sort(raw.begin(), raw.end()); vector<pair<u64,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 都是两个大质数的乘积）。

这张表里最有意思的一行是"n=10^9，10^5 组"。试除法要 30 秒，筛法只要 80 毫秒，而 Pollard-Rho 反而要 300 毫秒——因为 Pollard-Rho 单次的常数很大，对这么小的 n 来说，它的随机化开销还不如直接查表。

还有 n=10^6、10^5 组这一行，筛法依然碾压。这说明一个反直觉的结论：Pollard-Rho 的快是相对于大数而言的，对小数据它反而是最慢的。很多选手学了 Pollard-Rho 就想到处用，结果在小数据上被筛法吊打。

5.2 一个实用的选型决策树

我把上面的数据整理成一张判断流程，写在草稿纸上，赛场上照着走就行：

1. 先看 n 的上限。超过 10^12，直接上 Pollard-Rho，别犹豫。
2. n 不超过 10^12，再看查询次数。查询少于 100 组，用优化试除法（或用质数表试除）。
3. 查询成百上千组，且 n 上限不超过 10^7，用线性筛 SPF。
4. 查询成百上千组，n 上限在 10^7 到 10^12 之间，用"筛质数 + 质数表试除"的混合方案。

这四步我不止一次在赛场上用，每次都能快速定位方向，省下大量纠结时间。

还有一点要提醒：如果题目本身还要求其他预处理（比如求欧拉函数、莫比乌斯函数、约数个数），那几乎必然要用线性筛，因为那些函数本来就是基于最小质因子递推的。分解质因数只是顺带的事，不要为了分解单独选算法。

6. 常见问题排查与实操心得

6.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 个数，每次查询一个区间，问区间内所有数的质因子种类数"。这种情况下，每次查询都现场分解是极大的浪费。

正确做法是一次性把所有数的分解结果存起来。具体来说，开一个vector<vector<int>> 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加上关掉，零成本。这个习惯一旦养成，边界问题的排查效率能提高一大截，比事后对着超时和错误答案瞎猜强得多。