这个标题我第一次看到时第一反应是这有什么好讲的2 的 N 次方不就是循环乘 2 吗找因子不就是从 2 开始除吗直到我在本地把 N 调到 100000看着输出窗口里越滚越长的数字又拿一个 19 位合数去分解等了三分钟没跑出结果才意识到这两个题根本不是签到题——它们是通往“大整数处理”和“大数分解”这两座深山的入口。这篇内容就围绕标题展开先讲 2 的 N 次方背后的大整数存储与加速思路再讲大整数因子分解的经典算法组合最后把我实际调试中踩过的坑整理成一份速查清单。适合刚学完 C/C 基础、开始接触算法竞赛或者工作中偶尔需要自己实现大数运算的读者。1. 两个题目背后藏的是同一套基本功1.1 “2 的 N 次方”看着是水题实则是高精度入门很多人学编程时写的第一个循环就是算 2 的 N 次方。但绝大多数教材只让你算到 N10、N20int 完全装得下。一旦把 N 提到 1000、10000int 连个零头都装不下——2 的 1000 次方大约有 302 位十进制数2 的 10000 次方有 3010 位。这时候你才意识到所谓“计算 2 的 N 次方”根本不是乘法的循环而是“高精度乘法”的入门题你必须自己想办法表示一个任意长度的整数然后在它上面做乘法。这个题目最好的地方在于它把高精度里最核心的两个问题一次性暴露出来了怎么存储一个超出基本数据类型范围的整数怎么在存储结构上实现乘法并正确处理进位这两个问题搞清楚了后面再遇到加法、减法、阶乘、大数取模都是一通百通的事。1.2 “大整数的因子”一个越界就失控的经典问题再看第二个小标题大整数的因子。因子这个概念本身不难但“大整数”三个字让难度完全变了。对一个小数比如 72手工分解就是 2×2×2×3×3。对 10^12 这种级别写个循环从 2 试除到平方根也还撑得住。可一旦数字到了 10^18 或者更大试除法在时间上直接失控——循环次数是平方根量级10^18 的平方根是 10^9一次循环哪怕只要 1 纳秒也要整整 1 秒以上何况每条指令远远不止 1 纳秒。这时候需要的东西就超出了“枚举”的范畴素性判定要用 Miller-Rabin因子搜索要用 Pollards Rho。这两套算法背后是费马小定理、二次探测定理和生日悖论每个都是数论里正经八百的硬知识。所以第二个题目真正的考点是你能不能从“暴力枚举”升级到“概率算法 数论定理”的思维。1.3 为什么这两个题目要放在一起把它们放在一起不是因为它们都属于“数学题”而是因为它们共享同一套内功第一都要求你正视基本数据类型的边界第二都要求你做复杂度分析而不是写完拉倒第三两者的经典解法里都大量用到“取模”和“快速幂”这两块拼图。学会了 2 的 N 次方你就掌握了快速幂掌握了快速幂Miller-Rabin 里的模幂运算就是现成的工具。这两个题目远比表面看起来连贯得多。2. 计算 2 的 N 次方从数组模拟到万进制提速2.1 为什么 int 和 long long 都存不下先从最朴素的问题问起为什么一定要绕开 int因为 int 通常只有 32 位能表示的最大值是 2147483647大约 2.1×10^9。long long 是 64 位最大到 9.2×10^18也就是 19 位十进制数。而 2 的 1000 次方有 302 位2 的 100000 次方有 30103 位——任何基本类型都装不下。你可能会说那用 Python 啊Python 的大整数是原生支持的一行2**n就完事了。确实脚本语言帮我们屏蔽了底层但这也正是问题所在你根本不知道它是怎么做到的。用 C/C 自己实现一遍你才能真正理解“数组 进位”这套机制也才能在脑子里估算出一段代码的时间复杂度。生活里怎么比喻这件事就好比你手里只有一张写着“最大 2 的 31 次方”的小纸条现在要记录一个 300 位的数字你只能把纸条拼接起来一张存几位串成一条长纸条。数组模拟大整数本质就是这个“拼接纸条”的过程。2.2 数组模拟竖式乘法先把正确性做出来最容易理解的做法是用一个数组代表大整数数组的每一位代表十进制的一位。我习惯把最低位放在数组下标 0 的位置也就是低位在前。这样每次乘 2 的时候进位是向“数组尾部更高位”方向传的直接在末尾 push 新位就行特别顺手。核心代码只有十几行#include iostream #include vector using namespace std; int main() { int n 1000; vectorint a(1, 1); // a[0] 1最低位在前 for (int i 0; i n; i) { // 连续乘 n 次 2 int carry 0; for (int j 0; j (int)a.size(); j) { int t a[j] * 2 carry; // 当前位乘 2加上从低位来的进位 a[j] t % 10; // 当前位只保留个位 carry t / 10; // 其余部分作为进位给更高位 } if (carry) a.push_back(carry); // 最高位还有进位数组扩容一位 } for (int i (int)a.size() - 1; i 0; i--) { cout a[i]; } cout endl; return 0; }这段代码有几个值得注意的点。第一carry每次最多是 1因为任何一位乘以 2 之后最多向前进 1但在更通用的乘法里进位可能很大所以不能默认它是 1。第二数组先存低位打印时从尾部往前倒序输出这个习惯一开始就要养成否则后面写万进制时会乱。第三t a[j] * 2 carry不会超过 19int 完全够用但如果你以后做的是大数乘以大数就要小心中间结果溢出这里乘的是 2 所以安全。这段代码在 N 较小比如几千时完全没问题。但它的时间复杂度是多少外层循环 N 次内层循环每次遍历当前位数。2^N 的位数大约是N * log10(2) ≈ 0.301 * N所以总操作量大约是N * 0.301 * N 0.3 * N^2。N100000 时大约是 3×10^9 次操作C 也要跑好几秒甚至更久。这还不是最致命的最大问题的是这个复杂度根本扛不住更大的 N。所以接下来要想办法提速。2.3 万进制优化同样的循环性能翻好几倍一个立刻见效的优化是不要用十进制一位一位存而是用万进制也就是数组的每个“格子”存 0~9999 之间的数。这样数组长度一下子变成原来的四分之一内层循环次数也变成原来的四分之一再加上每次乘法操作对象是万位数字省略了反复逐位处理的过程整体性能明显提升。你可能会问为什么偏偏是 10000 而不是 10 的更大次方因为 10000×10000 再加进位也不会超过 int 的范围100000×100000 就可能超出 32 位 int 了。选 10000 是为了在“单个格子容量大”和“乘法不溢出”之间取一个安全值。如果你用的是 64 位类型可以参考这个思路选 10^8 甚至 10^9道理完全一样。看代码#include bits/stdc.h using namespace std; const int BASE 10000; int main() { int n; cin n; vectorint a(1, 1); // 最低位在前 for (int i 0; i n; i) { int carry 0; for (int j 0; j (int)a.size(); j) { a[j] a[j] * 2 carry; carry a[j] / BASE; // 超过 10000 的部分进位 a[j] % BASE; } if (carry) a.push_back(carry); } cout a.back(); // 最高位原样输出 for (int i (int)a.size() - 2; i 0; i--) { cout setw(4) setfill(0) a[i]; // 其余位补前导零到 4 位 } cout \n; return 0; }输出部分是最容易出错的地方。万进制数组里每个格子对应十进制里的 4 位但除最高位以外其余格子如果值是 12实际表示的是“0012”必须补前导零。比如数组[1, 10000, 12]实际数字是1_0000_0012也就是 100000012而不是11000012。我早期写这类代码时十次有八次栽在这个输出补零上。性能上万进制把数组长度压缩到原来的四分之一内层循环量也随之降到四分之一实际测试 N100000 时十进制版本可能要 3 秒以上万进制版本在同机器上能压到 1 秒以内。但要注意它还是 O(N^2) 的算法只是常数小了。真要算 2 的几百万次方就得用快速幂配合 FFT/NTT 之类的手段那属于另一个难度层次。2.4 指数再大也不慌快速幂和它的应用场合如果题目要求的不只是“完整输出 2 的 N 次方”而是“求 2^N 对某个数取模”那就绕开了高精度存储直接用快速幂。快速幂的核心思想是把指数 N 拆成二进制从上往下按位处理。比如求 2^1313 的二进制是 1101也就是 2^13 2^8 × 2^4 × 2^1。只要预处理出 2^1、2^2、2^4、2^8再按二进制位把这些项乘起来就行。typedef long long ll; ll qpow(ll a, ll b, ll mod) { ll res 1; while (b 0) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }这段代码你会在后面 Miller-Rabin 里原封不动地再用一次所以最好一次写熟。需要注意当 mod 接近 10^18 量级时res * a这一步本身就会溢出 long long这时候要么用__int128做中间类型要么写一个快速乘类似快速幂的加法版本后面我会展开讲。3. 大整数因子分解从试除到随机化算法3.1 试除法以及它的两个常见优化先把最基础的试除法写出来。对一个整数 n从 2 开始逐个试除只要某个数能整除就把它除干净然后继续。正确性来自算术基本定理任何整数都能唯一分解成素数的乘积。代码不长但已经比很多人凭感觉写的版本健壮很多vectorll trial_division(ll n) { vectorll factors; for (ll d 2; d * d n; d) { while (n % d 0) { factors.push_back(d); n / d; } } if (n 1) factors.push_back(n); return factors; }这里第一坑是d * d n有可能溢出。如果 n 接近 10^18d 到 10^9 时d*d就是 10^18刚好在 long long 范围内但 n 更大的话比如 10^19 量级d*d就爆了。稳妥写法是d n / d。常见的进一步剪枝有两个方向。第一跳过偶数先单独处理 2然后 d 从 3 开始每次加 2循环量减半。第二使用 6k±1 模式因为大于 3 的素数都能写成 6k±1所以可以从 5 开始每次先试 i再试 i2然后 i6。写成代码是这样的vectorll trial_division_fast(ll n) { vectorll factors; while (n % 2 0) { factors.push_back(2); n / 2; } for (ll i 3; i n / i; i 2) { while (n % i 0) { factors.push_back(i); n / i; } } if (n 1) factors.push_back(n); return factors; }这个版本在 n10^12 时循环到 10^6 次秒过到 10^14循环到 10^7 次勉强能忍到 10^16 以上纯试除法就已经不现实了。这也是为什么我们需要概率算法。3.2 Miller-Rabin怎么快速判断“是不是素数”分解因子前先得知道一个数是不是素数。Miller-Rabin 是目前最实用的素性判定方案它建立在费马小定理之上如果 p 是素数那么对于任意 a都有 a^(p-1) ≡ 1 (mod p)。不过仅用费马小定理不够因为存在一类叫“卡迈克尔数”的合数对几乎所有 a 都能通过费马检测。所以 Miller-Rabin 还要引入二次探测定理如果 p 是奇素数那么方程 x^2 ≡ 1 (mod p) 只有两个解x ≡ 1 或 x ≡ -1。具体做法是先把 n-1 分解成d * 2^rd 是奇数。然后随机选一个底数 a先算x a^d mod n。如果 x 是 1 或 n-1这一轮通过否则不断把 x 平方最多平方 r-1 次如果中间某次变成 n-1这一轮也通过。如果始终没出现 n-1那 n 一定是合数。对 64 位以内的整数不需要真的随机选很多底数固定用一组小素数做底判定结果在数学上已经被验证足够准确。代码可以直接这样写ll mul_mod(ll a, ll b, ll m) { ll r 0; a % m; b % m; while (b 0) { if (b 1) r (r a) % m; a (a a) % m; b 1; } return r; } ll pow_mod(ll a, ll b, ll m) { ll r 1; while (b 0) { if (b 1) r mul_mod(r, a, m); a mul_mod(a, a, m); b 1; } return r; } bool Miller_Rabin(ll n) { if (n 2) return false; static ll bases[] {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}; for (ll p : bases) { if (n p) return true; if (n % p 0) return false; } ll d n - 1; int r 0; while ((d 1) 0) { d 1; r; } for (ll a : bases) { ll x pow_mod(a, d, n); if (x 1 || x n - 1) continue; bool ok false; for (int i 0; i r - 1; i) { x mul_mod(x, x, n); if (x n - 1) { ok true; break; } } if (!ok) return false; } return true; }这里mul_mod是关键。直接写a * b % m在 a、b 都接近 10^18 时会溢出 long long但用“加法版快速幂”来模拟乘法就不会出问题。如果编译器支持__int128也可以直接写成( __int128 )a * b % m性能更好代码更短。3.3 Pollards Rho用生日悖论撞开因子有了素性判定剩下来的问题就是在合数里找一个非平凡因子。这个看似简单的问题实际是大整数分解真正的难点。反直觉的是随机化在这里反而出奇地有效原理是生日悖论从 1 到 n 里随机取数大约取到 sqrt(n) 个就会出现重复而如果 n 有一个小因子 p那么随机序列在模 p 意义下会更快出现循环这个循环的期望长度只有 sqrt(p)远远小于 sqrt(n)。Pollards Rho 算法就利用这一点。它构造一个伪随机序列x_{k1} (x_k^2 c) mod n然后不断计算相邻两个数的差的绝对值与 n 的最大公约数。如果 gcd(|x_i - x_j|, n) 落在 1 和 n 之间就找到了一个非平凡因子。为了避免序列出现无限循环通常用 Floyd 判圈一个指针每次走一步另一个每次走两步类似链表里判断有没有环。这里的“为什么”值得展开一下。当 x_i 和 x_j 在模 p 的意义下相等时|x_i - x_j| 就包含因子 p所以它和 n 的 gcd 很可能就是 p 或 p 的倍数。而按生日悖论在模 p 下出现碰撞只需要 O(sqrt(p)) 步。所以整个算法的期望复杂度大约是 O(n^(1/4) * log n)对 64 位整数来说已经非常理想。代码是整套方案里最容易写错的部分之一ll Pollard_Rho(ll n) { if (n % 2 0) return 2; if (n % 3 0) return 3; static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); while (true) { ll c rng() % (n - 1) 1; ll x rng() % n; ll y x; ll d 1; auto f [](ll v) { return (mul_mod(v, v, n) c) % n; }; while (d 1) { x f(x); y f(f(y)); d gcd(x y ? x - y : y - x, n); } if (d ! n) return d; // 如果 d n说明这次随机种子没撞上因子换 c 重来 } }注意几点f(f(y))是让慢指针走一步、快指针走两步的写法gcd(x-y, n)里 x-y 可能为负这里用三元表达式取绝对值如果 gcd 结果是 n说明 x 和 y 在模 n 下撞成了同一个数这次随机失败换一个 c 重试。理论失败概率很低但代码里必须有重试机制。另外很多人会用rand()来生成随机数但rand()的周期和范围在 64 位问题里都不够用建议用mt19937_64。这一点在真实工程里尤其重要我在自己的项目里就因为rand()范围太小导致某些大数上反复重试、拖慢了好几秒。3.4 组合方案与完整代码至此可以拼出一套完整的因子分解流程先 Miller-Rabin 判断素数是素数就直接收集是合数就先用小素数预检再 Pollard-Rho 找一个因子然后递归分解两边。整个流程逻辑很清晰void factorize(ll n, vectorll ans) { if (n 1) return; if (Miller_Rabin(n)) { ans.push_back(n); return; } ll d Pollard_Rho(n); factorize(d, ans); factorize(n / d, ans); }实测下来这套组合对 64 位以内的整数10^18 量级基本可以做到毫秒或几十毫秒级分解。但如果把 n 变成 100 位的十进制大数同样的算法依然无能为力——那不是算法常数能解决的问题而是整个问题的计算复杂度决定的现代公钥加密也正建立在这个难度之上。4. 两个题放在一起练到底练什么4.1 共同内核大数表示、复杂度思维、随机化技巧把“计算 2 的 N 次方”和“大整数的因子”放在一起最核心的价值其实是让你完成三件事。一是建立“数据范围决定算法选型”的直觉。见到题目先问范围N 是 10 还是 100000n 是 10^9 还是 10^18范围不同算法完全不同。问清楚范围再动手比蒙着头写循环重要得多。二是掌握“中间结果溢出”的防范意识。万进制里单格乘 2 没事快速幂里res*a就可能爆 long longPollard-Rho 里mul_mod成了标配。这些坑不是靠记忆力而是靠你对每个运算的位数上限有概念才能避免。三是理解随机化为什么能解决确定性算法搞不定的问题。Pollard-Rho 不保证每次都在固定步数内成功但期望步数很好Miller-Rabin 不保证数学上绝对正确但错误概率可以压到忽略不计。设计算法时确定性不是唯一标准效率和可用性同样重要。4.2 真实世界中它们出现在哪这两个问题绝不只有竞赛价值。2 的 N 次方的高精度计算是所有大数运算库的底层原型你在某种语言里写BigInteger.pow(2, n)引擎内部干的事和我上面写的数组乘法并无本质差别。快速幂更是现代密码学的心脏——很多加密算法里的模幂运算就是用快速幂实现的。而大整数的因子分解则直接关系到一些加密方案的安全性设计者希望“拆解大整数”足够难难到攻击者花几十年也算不出来反过来研究如何更快地分解大整数也是在帮助整个体系校准安全参数。理解 Miller-Rabin 和 Pollard-Rho等于把这类问题的原理脉络摸了一遍。还有更接地气的场景某些哈希算法需要处理 128 位或 256 位的大整数运算某些数据处理系统需要在超过 64 位的中间结果上做取模和校验这些都绕不开大整数基本功。可以说这两个标题合在一起就是一本微型《大数运算实用手册》。4.3 顺带一提很多人会搜到的“连续因子”变体搜索“大整数 因子”的时候总有人会被带到一个相关但完全不同的题目——连续因子。最典型的就是某道很流行的竞赛训练题输入一个正整数 N要求输出 N 的最长连续因子序列。比如 N630可以分解成 3×5×6×7这一串 3、5、6、7 连续四个数相乘等于 630所以答案就是长度 4、起点 3。这个题和 Pollard-Rho 没关系因为它不要求把 N 彻底分解只需要在 sqrt(N) 范围内枚举每个可能的起点 i然后从 i 开始连乘只要乘积能整除 N 就一直往后扩。核心代码就是一个二重循环复杂度 O(sqrt(N) * 序列长度)。它考察的是枚举和剪枝不是数论。如果你搜到的是“因子分析法”或“影响因子”这类词那和这里的“因子”完全是两码事——前者是统计模型里的因子后者是期刊评价指标都不是整数意义下的因子。我在这里提一句主要是为了帮你少走弯路别拿着 Miller-Rabin 去套统计问题。5. 踩坑实录与调试清单5.1 四个我实际踩过的坑第一个坑是万进制输出忘补前导零。数组[1, 10000, 12]实际是大数100000012如果你图省事直接把每个元素连着打印会输出11000012整整错一位数字。正确做法是最高位原样输出其余位必须setw(4) setfill(0)补成 4 位。这个错在 N 较小时不会出现因为数组只有一个元素N 一旦超过 10000就会突然冒出来而且很难肉眼发现。第二个坑是试除法的d * d n。在 n 接近 long long 上限时d 到 10^9 以上d*d就溢出变成负数循环条件直接退出导致少除一个因子。这种错误不报错、不崩溃只在结果里多出一个本不该出现的“大素数因子”。我现在的习惯是统一写d n / d一次到位。第三个坑是 Miller-Rabin 里的模乘溢出。直接写a * b % m当 a 和 b 都接近 10^18 时中间结果会溢出。最省事的办法是用__int128如果没有__int128就得手写mul_mod。很多网上的模板没提这一点导致大家复制下来后在大数上偶发错误还以为是随机算法不稳定。第四个坑是 Pollard-Rho 的随机数生成。用rand()时它能覆盖的范围在 64 位整数面前太小导致随机种子不够分散部分输入会反复重试。换成mt19937_64并配合系统时间做种子问题立刻改善。另外while(d 1)循环里如果 x 和 y 撞上了gcd 会返回 n这时必须换 c 重试而不是继续循环否则程序会陷入死循环。5.2 自测清单提交前检查这六项我每次写完这类代码都会过一遍以下检查分享出来供参考N1 时输出是否为 2N0 时是否为 1很多题目允许 N0数组初始化为 1 直接输出即可。N1000 时输出的位数是否为 302用log10(2)*1000取整加一验证。万进制输出时随机选一个规模比如 N12345和 Python 的pow(2, N)逐位对拍。分解 72 时得到 [2,2,2,3,3]分解 1 时程序不崩返回空结果。用大素数比如 10^183 做 Miller-Rabin必须返回 true用相邻的合数做测试必须返回 false。Pollard-Rho 跑一个 2^61-1 的素数和它的若干倍观察是否能在合理时间内结束而不是死循环。最后说一个自己的实测心得这两个问题真正考验人的不是能不能写出代码而是写完之后有没有耐心去验证边界。我当年交作业时2 的 1000 次方输出少补了一位 0整道题全错后来把“输出前导补零”变成了肌肉记忆Pollard-Rho 又多跑了几十组随机数据才敢拿去对拍。别嫌这些细节碎高精度和数论算法这种东西隐蔽的错误往往比逻辑难缠得多。如果你也在练这类题建议把题目里的 N 依次调到 1、10、100、10000 各跑一遍成本极低回报极大。
大整数运算与因子分解：从高精度乘法到Pollard Rho实战
这个标题我第一次看到时第一反应是这有什么好讲的2 的 N 次方不就是循环乘 2 吗找因子不就是从 2 开始除吗直到我在本地把 N 调到 100000看着输出窗口里越滚越长的数字又拿一个 19 位合数去分解等了三分钟没跑出结果才意识到这两个题根本不是签到题——它们是通往“大整数处理”和“大数分解”这两座深山的入口。这篇内容就围绕标题展开先讲 2 的 N 次方背后的大整数存储与加速思路再讲大整数因子分解的经典算法组合最后把我实际调试中踩过的坑整理成一份速查清单。适合刚学完 C/C 基础、开始接触算法竞赛或者工作中偶尔需要自己实现大数运算的读者。1. 两个题目背后藏的是同一套基本功1.1 “2 的 N 次方”看着是水题实则是高精度入门很多人学编程时写的第一个循环就是算 2 的 N 次方。但绝大多数教材只让你算到 N10、N20int 完全装得下。一旦把 N 提到 1000、10000int 连个零头都装不下——2 的 1000 次方大约有 302 位十进制数2 的 10000 次方有 3010 位。这时候你才意识到所谓“计算 2 的 N 次方”根本不是乘法的循环而是“高精度乘法”的入门题你必须自己想办法表示一个任意长度的整数然后在它上面做乘法。这个题目最好的地方在于它把高精度里最核心的两个问题一次性暴露出来了怎么存储一个超出基本数据类型范围的整数怎么在存储结构上实现乘法并正确处理进位这两个问题搞清楚了后面再遇到加法、减法、阶乘、大数取模都是一通百通的事。1.2 “大整数的因子”一个越界就失控的经典问题再看第二个小标题大整数的因子。因子这个概念本身不难但“大整数”三个字让难度完全变了。对一个小数比如 72手工分解就是 2×2×2×3×3。对 10^12 这种级别写个循环从 2 试除到平方根也还撑得住。可一旦数字到了 10^18 或者更大试除法在时间上直接失控——循环次数是平方根量级10^18 的平方根是 10^9一次循环哪怕只要 1 纳秒也要整整 1 秒以上何况每条指令远远不止 1 纳秒。这时候需要的东西就超出了“枚举”的范畴素性判定要用 Miller-Rabin因子搜索要用 Pollards Rho。这两套算法背后是费马小定理、二次探测定理和生日悖论每个都是数论里正经八百的硬知识。所以第二个题目真正的考点是你能不能从“暴力枚举”升级到“概率算法 数论定理”的思维。1.3 为什么这两个题目要放在一起把它们放在一起不是因为它们都属于“数学题”而是因为它们共享同一套内功第一都要求你正视基本数据类型的边界第二都要求你做复杂度分析而不是写完拉倒第三两者的经典解法里都大量用到“取模”和“快速幂”这两块拼图。学会了 2 的 N 次方你就掌握了快速幂掌握了快速幂Miller-Rabin 里的模幂运算就是现成的工具。这两个题目远比表面看起来连贯得多。2. 计算 2 的 N 次方从数组模拟到万进制提速2.1 为什么 int 和 long long 都存不下先从最朴素的问题问起为什么一定要绕开 int因为 int 通常只有 32 位能表示的最大值是 2147483647大约 2.1×10^9。long long 是 64 位最大到 9.2×10^18也就是 19 位十进制数。而 2 的 1000 次方有 302 位2 的 100000 次方有 30103 位——任何基本类型都装不下。你可能会说那用 Python 啊Python 的大整数是原生支持的一行2**n就完事了。确实脚本语言帮我们屏蔽了底层但这也正是问题所在你根本不知道它是怎么做到的。用 C/C 自己实现一遍你才能真正理解“数组 进位”这套机制也才能在脑子里估算出一段代码的时间复杂度。生活里怎么比喻这件事就好比你手里只有一张写着“最大 2 的 31 次方”的小纸条现在要记录一个 300 位的数字你只能把纸条拼接起来一张存几位串成一条长纸条。数组模拟大整数本质就是这个“拼接纸条”的过程。2.2 数组模拟竖式乘法先把正确性做出来最容易理解的做法是用一个数组代表大整数数组的每一位代表十进制的一位。我习惯把最低位放在数组下标 0 的位置也就是低位在前。这样每次乘 2 的时候进位是向“数组尾部更高位”方向传的直接在末尾 push 新位就行特别顺手。核心代码只有十几行#include iostream #include vector using namespace std; int main() { int n 1000; vectorint a(1, 1); // a[0] 1最低位在前 for (int i 0; i n; i) { // 连续乘 n 次 2 int carry 0; for (int j 0; j (int)a.size(); j) { int t a[j] * 2 carry; // 当前位乘 2加上从低位来的进位 a[j] t % 10; // 当前位只保留个位 carry t / 10; // 其余部分作为进位给更高位 } if (carry) a.push_back(carry); // 最高位还有进位数组扩容一位 } for (int i (int)a.size() - 1; i 0; i--) { cout a[i]; } cout endl; return 0; }这段代码有几个值得注意的点。第一carry每次最多是 1因为任何一位乘以 2 之后最多向前进 1但在更通用的乘法里进位可能很大所以不能默认它是 1。第二数组先存低位打印时从尾部往前倒序输出这个习惯一开始就要养成否则后面写万进制时会乱。第三t a[j] * 2 carry不会超过 19int 完全够用但如果你以后做的是大数乘以大数就要小心中间结果溢出这里乘的是 2 所以安全。这段代码在 N 较小比如几千时完全没问题。但它的时间复杂度是多少外层循环 N 次内层循环每次遍历当前位数。2^N 的位数大约是N * log10(2) ≈ 0.301 * N所以总操作量大约是N * 0.301 * N 0.3 * N^2。N100000 时大约是 3×10^9 次操作C 也要跑好几秒甚至更久。这还不是最致命的最大问题的是这个复杂度根本扛不住更大的 N。所以接下来要想办法提速。2.3 万进制优化同样的循环性能翻好几倍一个立刻见效的优化是不要用十进制一位一位存而是用万进制也就是数组的每个“格子”存 0~9999 之间的数。这样数组长度一下子变成原来的四分之一内层循环次数也变成原来的四分之一再加上每次乘法操作对象是万位数字省略了反复逐位处理的过程整体性能明显提升。你可能会问为什么偏偏是 10000 而不是 10 的更大次方因为 10000×10000 再加进位也不会超过 int 的范围100000×100000 就可能超出 32 位 int 了。选 10000 是为了在“单个格子容量大”和“乘法不溢出”之间取一个安全值。如果你用的是 64 位类型可以参考这个思路选 10^8 甚至 10^9道理完全一样。看代码#include bits/stdc.h using namespace std; const int BASE 10000; int main() { int n; cin n; vectorint a(1, 1); // 最低位在前 for (int i 0; i n; i) { int carry 0; for (int j 0; j (int)a.size(); j) { a[j] a[j] * 2 carry; carry a[j] / BASE; // 超过 10000 的部分进位 a[j] % BASE; } if (carry) a.push_back(carry); } cout a.back(); // 最高位原样输出 for (int i (int)a.size() - 2; i 0; i--) { cout setw(4) setfill(0) a[i]; // 其余位补前导零到 4 位 } cout \n; return 0; }输出部分是最容易出错的地方。万进制数组里每个格子对应十进制里的 4 位但除最高位以外其余格子如果值是 12实际表示的是“0012”必须补前导零。比如数组[1, 10000, 12]实际数字是1_0000_0012也就是 100000012而不是11000012。我早期写这类代码时十次有八次栽在这个输出补零上。性能上万进制把数组长度压缩到原来的四分之一内层循环量也随之降到四分之一实际测试 N100000 时十进制版本可能要 3 秒以上万进制版本在同机器上能压到 1 秒以内。但要注意它还是 O(N^2) 的算法只是常数小了。真要算 2 的几百万次方就得用快速幂配合 FFT/NTT 之类的手段那属于另一个难度层次。2.4 指数再大也不慌快速幂和它的应用场合如果题目要求的不只是“完整输出 2 的 N 次方”而是“求 2^N 对某个数取模”那就绕开了高精度存储直接用快速幂。快速幂的核心思想是把指数 N 拆成二进制从上往下按位处理。比如求 2^1313 的二进制是 1101也就是 2^13 2^8 × 2^4 × 2^1。只要预处理出 2^1、2^2、2^4、2^8再按二进制位把这些项乘起来就行。typedef long long ll; ll qpow(ll a, ll b, ll mod) { ll res 1; while (b 0) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }这段代码你会在后面 Miller-Rabin 里原封不动地再用一次所以最好一次写熟。需要注意当 mod 接近 10^18 量级时res * a这一步本身就会溢出 long long这时候要么用__int128做中间类型要么写一个快速乘类似快速幂的加法版本后面我会展开讲。3. 大整数因子分解从试除到随机化算法3.1 试除法以及它的两个常见优化先把最基础的试除法写出来。对一个整数 n从 2 开始逐个试除只要某个数能整除就把它除干净然后继续。正确性来自算术基本定理任何整数都能唯一分解成素数的乘积。代码不长但已经比很多人凭感觉写的版本健壮很多vectorll trial_division(ll n) { vectorll factors; for (ll d 2; d * d n; d) { while (n % d 0) { factors.push_back(d); n / d; } } if (n 1) factors.push_back(n); return factors; }这里第一坑是d * d n有可能溢出。如果 n 接近 10^18d 到 10^9 时d*d就是 10^18刚好在 long long 范围内但 n 更大的话比如 10^19 量级d*d就爆了。稳妥写法是d n / d。常见的进一步剪枝有两个方向。第一跳过偶数先单独处理 2然后 d 从 3 开始每次加 2循环量减半。第二使用 6k±1 模式因为大于 3 的素数都能写成 6k±1所以可以从 5 开始每次先试 i再试 i2然后 i6。写成代码是这样的vectorll trial_division_fast(ll n) { vectorll factors; while (n % 2 0) { factors.push_back(2); n / 2; } for (ll i 3; i n / i; i 2) { while (n % i 0) { factors.push_back(i); n / i; } } if (n 1) factors.push_back(n); return factors; }这个版本在 n10^12 时循环到 10^6 次秒过到 10^14循环到 10^7 次勉强能忍到 10^16 以上纯试除法就已经不现实了。这也是为什么我们需要概率算法。3.2 Miller-Rabin怎么快速判断“是不是素数”分解因子前先得知道一个数是不是素数。Miller-Rabin 是目前最实用的素性判定方案它建立在费马小定理之上如果 p 是素数那么对于任意 a都有 a^(p-1) ≡ 1 (mod p)。不过仅用费马小定理不够因为存在一类叫“卡迈克尔数”的合数对几乎所有 a 都能通过费马检测。所以 Miller-Rabin 还要引入二次探测定理如果 p 是奇素数那么方程 x^2 ≡ 1 (mod p) 只有两个解x ≡ 1 或 x ≡ -1。具体做法是先把 n-1 分解成d * 2^rd 是奇数。然后随机选一个底数 a先算x a^d mod n。如果 x 是 1 或 n-1这一轮通过否则不断把 x 平方最多平方 r-1 次如果中间某次变成 n-1这一轮也通过。如果始终没出现 n-1那 n 一定是合数。对 64 位以内的整数不需要真的随机选很多底数固定用一组小素数做底判定结果在数学上已经被验证足够准确。代码可以直接这样写ll mul_mod(ll a, ll b, ll m) { ll r 0; a % m; b % m; while (b 0) { if (b 1) r (r a) % m; a (a a) % m; b 1; } return r; } ll pow_mod(ll a, ll b, ll m) { ll r 1; while (b 0) { if (b 1) r mul_mod(r, a, m); a mul_mod(a, a, m); b 1; } return r; } bool Miller_Rabin(ll n) { if (n 2) return false; static ll bases[] {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}; for (ll p : bases) { if (n p) return true; if (n % p 0) return false; } ll d n - 1; int r 0; while ((d 1) 0) { d 1; r; } for (ll a : bases) { ll x pow_mod(a, d, n); if (x 1 || x n - 1) continue; bool ok false; for (int i 0; i r - 1; i) { x mul_mod(x, x, n); if (x n - 1) { ok true; break; } } if (!ok) return false; } return true; }这里mul_mod是关键。直接写a * b % m在 a、b 都接近 10^18 时会溢出 long long但用“加法版快速幂”来模拟乘法就不会出问题。如果编译器支持__int128也可以直接写成( __int128 )a * b % m性能更好代码更短。3.3 Pollards Rho用生日悖论撞开因子有了素性判定剩下来的问题就是在合数里找一个非平凡因子。这个看似简单的问题实际是大整数分解真正的难点。反直觉的是随机化在这里反而出奇地有效原理是生日悖论从 1 到 n 里随机取数大约取到 sqrt(n) 个就会出现重复而如果 n 有一个小因子 p那么随机序列在模 p 意义下会更快出现循环这个循环的期望长度只有 sqrt(p)远远小于 sqrt(n)。Pollards Rho 算法就利用这一点。它构造一个伪随机序列x_{k1} (x_k^2 c) mod n然后不断计算相邻两个数的差的绝对值与 n 的最大公约数。如果 gcd(|x_i - x_j|, n) 落在 1 和 n 之间就找到了一个非平凡因子。为了避免序列出现无限循环通常用 Floyd 判圈一个指针每次走一步另一个每次走两步类似链表里判断有没有环。这里的“为什么”值得展开一下。当 x_i 和 x_j 在模 p 的意义下相等时|x_i - x_j| 就包含因子 p所以它和 n 的 gcd 很可能就是 p 或 p 的倍数。而按生日悖论在模 p 下出现碰撞只需要 O(sqrt(p)) 步。所以整个算法的期望复杂度大约是 O(n^(1/4) * log n)对 64 位整数来说已经非常理想。代码是整套方案里最容易写错的部分之一ll Pollard_Rho(ll n) { if (n % 2 0) return 2; if (n % 3 0) return 3; static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); while (true) { ll c rng() % (n - 1) 1; ll x rng() % n; ll y x; ll d 1; auto f [](ll v) { return (mul_mod(v, v, n) c) % n; }; while (d 1) { x f(x); y f(f(y)); d gcd(x y ? x - y : y - x, n); } if (d ! n) return d; // 如果 d n说明这次随机种子没撞上因子换 c 重来 } }注意几点f(f(y))是让慢指针走一步、快指针走两步的写法gcd(x-y, n)里 x-y 可能为负这里用三元表达式取绝对值如果 gcd 结果是 n说明 x 和 y 在模 n 下撞成了同一个数这次随机失败换一个 c 重试。理论失败概率很低但代码里必须有重试机制。另外很多人会用rand()来生成随机数但rand()的周期和范围在 64 位问题里都不够用建议用mt19937_64。这一点在真实工程里尤其重要我在自己的项目里就因为rand()范围太小导致某些大数上反复重试、拖慢了好几秒。3.4 组合方案与完整代码至此可以拼出一套完整的因子分解流程先 Miller-Rabin 判断素数是素数就直接收集是合数就先用小素数预检再 Pollard-Rho 找一个因子然后递归分解两边。整个流程逻辑很清晰void factorize(ll n, vectorll ans) { if (n 1) return; if (Miller_Rabin(n)) { ans.push_back(n); return; } ll d Pollard_Rho(n); factorize(d, ans); factorize(n / d, ans); }实测下来这套组合对 64 位以内的整数10^18 量级基本可以做到毫秒或几十毫秒级分解。但如果把 n 变成 100 位的十进制大数同样的算法依然无能为力——那不是算法常数能解决的问题而是整个问题的计算复杂度决定的现代公钥加密也正建立在这个难度之上。4. 两个题放在一起练到底练什么4.1 共同内核大数表示、复杂度思维、随机化技巧把“计算 2 的 N 次方”和“大整数的因子”放在一起最核心的价值其实是让你完成三件事。一是建立“数据范围决定算法选型”的直觉。见到题目先问范围N 是 10 还是 100000n 是 10^9 还是 10^18范围不同算法完全不同。问清楚范围再动手比蒙着头写循环重要得多。二是掌握“中间结果溢出”的防范意识。万进制里单格乘 2 没事快速幂里res*a就可能爆 long longPollard-Rho 里mul_mod成了标配。这些坑不是靠记忆力而是靠你对每个运算的位数上限有概念才能避免。三是理解随机化为什么能解决确定性算法搞不定的问题。Pollard-Rho 不保证每次都在固定步数内成功但期望步数很好Miller-Rabin 不保证数学上绝对正确但错误概率可以压到忽略不计。设计算法时确定性不是唯一标准效率和可用性同样重要。4.2 真实世界中它们出现在哪这两个问题绝不只有竞赛价值。2 的 N 次方的高精度计算是所有大数运算库的底层原型你在某种语言里写BigInteger.pow(2, n)引擎内部干的事和我上面写的数组乘法并无本质差别。快速幂更是现代密码学的心脏——很多加密算法里的模幂运算就是用快速幂实现的。而大整数的因子分解则直接关系到一些加密方案的安全性设计者希望“拆解大整数”足够难难到攻击者花几十年也算不出来反过来研究如何更快地分解大整数也是在帮助整个体系校准安全参数。理解 Miller-Rabin 和 Pollard-Rho等于把这类问题的原理脉络摸了一遍。还有更接地气的场景某些哈希算法需要处理 128 位或 256 位的大整数运算某些数据处理系统需要在超过 64 位的中间结果上做取模和校验这些都绕不开大整数基本功。可以说这两个标题合在一起就是一本微型《大数运算实用手册》。4.3 顺带一提很多人会搜到的“连续因子”变体搜索“大整数 因子”的时候总有人会被带到一个相关但完全不同的题目——连续因子。最典型的就是某道很流行的竞赛训练题输入一个正整数 N要求输出 N 的最长连续因子序列。比如 N630可以分解成 3×5×6×7这一串 3、5、6、7 连续四个数相乘等于 630所以答案就是长度 4、起点 3。这个题和 Pollard-Rho 没关系因为它不要求把 N 彻底分解只需要在 sqrt(N) 范围内枚举每个可能的起点 i然后从 i 开始连乘只要乘积能整除 N 就一直往后扩。核心代码就是一个二重循环复杂度 O(sqrt(N) * 序列长度)。它考察的是枚举和剪枝不是数论。如果你搜到的是“因子分析法”或“影响因子”这类词那和这里的“因子”完全是两码事——前者是统计模型里的因子后者是期刊评价指标都不是整数意义下的因子。我在这里提一句主要是为了帮你少走弯路别拿着 Miller-Rabin 去套统计问题。5. 踩坑实录与调试清单5.1 四个我实际踩过的坑第一个坑是万进制输出忘补前导零。数组[1, 10000, 12]实际是大数100000012如果你图省事直接把每个元素连着打印会输出11000012整整错一位数字。正确做法是最高位原样输出其余位必须setw(4) setfill(0)补成 4 位。这个错在 N 较小时不会出现因为数组只有一个元素N 一旦超过 10000就会突然冒出来而且很难肉眼发现。第二个坑是试除法的d * d n。在 n 接近 long long 上限时d 到 10^9 以上d*d就溢出变成负数循环条件直接退出导致少除一个因子。这种错误不报错、不崩溃只在结果里多出一个本不该出现的“大素数因子”。我现在的习惯是统一写d n / d一次到位。第三个坑是 Miller-Rabin 里的模乘溢出。直接写a * b % m当 a 和 b 都接近 10^18 时中间结果会溢出。最省事的办法是用__int128如果没有__int128就得手写mul_mod。很多网上的模板没提这一点导致大家复制下来后在大数上偶发错误还以为是随机算法不稳定。第四个坑是 Pollard-Rho 的随机数生成。用rand()时它能覆盖的范围在 64 位整数面前太小导致随机种子不够分散部分输入会反复重试。换成mt19937_64并配合系统时间做种子问题立刻改善。另外while(d 1)循环里如果 x 和 y 撞上了gcd 会返回 n这时必须换 c 重试而不是继续循环否则程序会陷入死循环。5.2 自测清单提交前检查这六项我每次写完这类代码都会过一遍以下检查分享出来供参考N1 时输出是否为 2N0 时是否为 1很多题目允许 N0数组初始化为 1 直接输出即可。N1000 时输出的位数是否为 302用log10(2)*1000取整加一验证。万进制输出时随机选一个规模比如 N12345和 Python 的pow(2, N)逐位对拍。分解 72 时得到 [2,2,2,3,3]分解 1 时程序不崩返回空结果。用大素数比如 10^183 做 Miller-Rabin必须返回 true用相邻的合数做测试必须返回 false。Pollard-Rho 跑一个 2^61-1 的素数和它的若干倍观察是否能在合理时间内结束而不是死循环。最后说一个自己的实测心得这两个问题真正考验人的不是能不能写出代码而是写完之后有没有耐心去验证边界。我当年交作业时2 的 1000 次方输出少补了一位 0整道题全错后来把“输出前导补零”变成了肌肉记忆Pollard-Rho 又多跑了几十组随机数据才敢拿去对拍。别嫌这些细节碎高精度和数论算法这种东西隐蔽的错误往往比逻辑难缠得多。如果你也在练这类题建议把题目里的 N 依次调到 1、10、100、10000 各跑一遍成本极低回报极大。
