核心概述
整数因数分解（Integer Factorization）：在 64 位范围内常用“Pollard–Rho + Miller–Rabin”组合，配合小素数试除与安全模乘，能高效分解无符号 64 位整数。期望复杂度近似 n^{1/4}，实际非常快。
原文引述
Description: Pollard–Rho factorization for 64-bit integers, using Miller–Rabin primality test and safe 128-bit or mulmod arithmetic; returns multiset of prime factors. Time: Heuristic ~ n^{1/4} per hard composite; very fast in practice for 64-bit
展开阐述
-
函数/接口（据实现）
- bool isPrime(u64 n)：Miller–Rabin 素性测试（使用对 64 位确定性的底集合）。
- u64 rho(u64 n)：Pollard–Rho 寻找非平凡因子（失败时换随机常数/起点重试）。
- void factor(u64 n, vector
& fac)：将 n 的素因子（含重数）加入 fac；常返回排序后的因子表。 - 可选：map<u64,int> compress(vector
& fac)：统计质因子与幂次。
-
核心思路
- 小试除：对小素数（如 ≤1e6）或小步长预筛，快速去掉微小因子，减轻后续压力（参见 082-数论-埃拉托斯特尼筛、085-数论-快速筛)。
- Miller–Rabin：将 n−1 写成 d·2^s，测试若干底 a 的 a^d, a^{2d}, … 是否命中 1 或 −1（mod n）；未命中则判合数（见 087-数论-米勒拉宾）。
- Pollard–Rho：构造迭代 f(x)=x^2+c mod n，使用 Floyd/Brent 判环；周期内 |x−y| 与 n 的 gcd 若 ∈(1,n) 则得非平凡因子；失败更换 c/起点/策略重试。
- 递归分解：若得到因子 d，则递归 factor(d) 与 factor(n/d)，以 isPrime 为叶判定。
- 安全模运算：幂与乘法需避免溢出，使用 128 位或自定义 mulmod（参见 090-数论-长整型模乘 与 091-数论-模幂）。
-
输出语义
- fac：包含所有质因子（含重数），常排序后使用；
- 压缩后可得 n = ∏ p_i^{e_i} 的表示，便于约数枚举、φ/σ 计算等。
-
复杂度
- 试除：O(π(B))；Rho 对“困难合数”期望 ~ n^{1/4}；64 位范围内通常毫秒级完成。
- Miller–Rabin 与模幂、模乘皆为 O(log n) 级别。
-
使用与注意
- 处理边界：n ∈ {0,1} 特判；偶数直接分出 2。
- 随机性：Rho 需要良好随机常数/起点；Brent 变体更稳健。
- 底集合：为 64 位选可证明确定性的底集合；更大范围需调整底集合或转为概率判定。
- 排序与去重：输出前可 sort(fac)，再统计幂次，避免下游重复计算。
- 溢出与类型：中间计算用 128 位或显式 mulmod，防止乘法溢出。