试除法适合n≤10¹²的大整数；超过该规模因最坏需√n次循环而不可接受，且须边试除边更新n、正确处理剩余大质数。
试除法适合什么规模的大整数？
试除法只适用于 n 在 1012 以内的情况——超过这个量级，最坏要跑 √n 次循环，实际已不可接受。它本质是暴力：从 2 枚举到 √n，遇到能整除的就记为因子，再持续除尽该因子。
常见错误现象：n 是大质数（比如 1012+39），试除完 √n 后漏掉它本身；或者没处理重复因子，导致同一个质因子只记录一次但没除干净。
- 必须边试除边更新
n，每次找到因子d就循环n /= d直到不能整除 - 枚举上限用
(long long)sqrt(n) + 1，但注意浮点误差，更稳妥是写成d * d - 循环结束后若
n > 1，说明剩余的n就是最后一个质因子（且必然为质数）
Pollard Rho 怎么避免无限循环和错误返回？
Pollard Rho 是对付 1012～1018 级合数的主力，但它不是确定性算法：单次运行可能失败、卡死或返回非真因子（比如 1 或原数）。核心靠随机化 + Floyd 判圈，但实现细节极易翻车。
典型坑：__gcd(abs(x - y), n) 返回 1 或 n 时没重试，直接当作因子用了；或者用 rand() 而没设 srand(time(0))，导致每次跑都一样，失败后永远失败。
立即学习“C++免费学习笔记（深入）”；
- 必须在外层加重试循环，每次换不同初始值
x0和函数参数c（比如从 1 开始递增） - 内部 Floyd 循环中，每若干步（如 128 次迭代）就计算一次
g = __gcd(abs(x - y), n)，若g == 1继续，若g == n说明本轮失败，跳出重来 - 使用
mt19937替代rand()，避免低质量随机数拖慢收敛
如何把试除法和 Pollard Rho 串成完整分解流程？
没人单独用 Pollard Rho 处理所有情况——它对小因子效率反而不如试除，还可能把 4 分解成 2×2 再卡住。实用策略是分层：先快速筛掉小因子，再用 Pollard Rho 攻坚剩余大合数。
使用场景：输入 n 可能含多个数量级差异极大的因子（例如 n = 2^10 * 1000000007 * 982451653999），需稳定输出全部质因子（可重复）。
- 先用试除法处理所有 ≤ 10⁶ 的因子（预筛质数不必要，直接枚举 2 和奇数即可）
- 试除后若剩余
n == 1，结束；若n是质数（可用 Miller-Rabin 快速判断），直接加入结果 - 否则调用 Pollard Rho 分解该剩余部分，递归处理两个返回因子（注意：Rho 返回的不一定是质数，得继续分解）
- Miller-Rabin 必须写对：底数选 {2, 325, 9375, 28178, 450775, 9780504, 1795265022} 可覆盖 64 位整数
为什么 64 位整数乘法容易溢出，怎么安全算 (a * b) % n？
Pollard Rho 里频繁出现 (x * x + c) % n，当 x 接近 10⁹ 时，x * x 就超 long long（约 9×10¹⁸），直接乘会溢出变负，再取模毫无意义。这不是“性能问题”，是正确性红线。
错误写法：(a % n) * (b % n) % n —— 中间乘积仍溢出；正确做法是模拟竖式乘法或用内置扩展指令。
- 手写
mul_mod(a, b, n)：用__int128（GCC 支持）最简，return (__int128)a * b % n - 无
__int128时用倍增法（类似快速幂）：把b拆成二进制，每次累加a * 2^k mod n，用加法代替乘法 - 切勿在
mul_mod里漏判n == 0或传入负数——Pollard Rho 中n永远 ≥ 2，但调试时可能传错
真正麻烦的从来不是算法逻辑，而是 mul_mod 写错、Miller-Rabin 底数漏掉、或者递归没设终止条件导致栈溢出——这些地方一错，整个分解就静默失效。
