企业官网建设流程全解析

直接从一个我至今记得很清楚的场景说起。几年前接手一个需要反复做模幂运算的模块，参数里的指数是十的十八次方量级，我一开始想都没想就写了最朴素的循环乘法，本地跑小数据一切正常，一上真实规模直接卡死，日志半天不出一行。那次之后我才认真把快速幂这套东西从原理到实现彻底捋了一遍。快速幂不是什么新东西，任何一个刷过算法题的人都能背出那七八行代码，但真正把它用对、用稳、用到矩阵和工程场景里，中间隔着的坑比想象中多得多。这篇内容就是把这些年关于快速幂的理解、踩坑和变体整理出来：从二进制分解的数学本质，到取模运算里的溢出陷阱，再到矩阵快速幂怎么把线性递推压进对数时间，最后聊几个真实工程里它出现的地方。适合刚接触算法的新手当作完整梳理，也适合有基础的人补齐那些教程里从来不写的边界细节。

1. 从一次超时说起：为什么求幂这件事值得单独设计算法

1.1 朴素幂运算的代价到底有多大

先算一笔账。计算 a 的 n 次方，最直觉的做法是累乘：拿一个变量存结果，初始为 1，然后循环 n 次，每次都乘一个 a。这个算法的时间复杂度是 O(n)，看起来只是个线性复杂度，好像没什么大不了。问题在于 n 的取值范围经常不是我们脑子里默认的"几十几百"。

现代 CPU 做一次 64 位整数乘法大致在纳秒级别，配合循环开销，一秒内能完成的乘法次数在 10^8 到 10^9 这个量级。当 n 只有 10^6 时，朴素算法几十毫秒就跑完了，你完全感觉不到问题；但当 n 变成 10^9，你就需要整整一秒以上；n 到 10^18，那就是按年计算的量级了。而 10^18 这个数量级恰恰是很多场景的常态：日期时间戳的差值、加密参数、组合计数的指数、递推题的项数。

我当时的错误就在于把"指数大"和"结果大"混为一谈了。指数大不代表结果大——只要取模，结果永远被压在模数以下，问题的规模全部集中在指数的位数上。而指数的位数只有 log2(n) 那么多，10^18 也不过 60 位。快速幂的核心洞察就是：把工作量从"指数的大小"转移到"指数的位数"上，这是从 O(n) 到 O(log n) 的降维打击，60 次迭代对 10^18 次迭代，差距不是优化，是能不能跑的问题。

1.2 二进制分解：把指数拆成 2 的幂之和

任何一个正整数都能唯一地表示成若干个 2 的幂之和，这就是二进制表示的定义。比如 13 = 8 + 4 + 1，写成二进制是 1101。这个事实本身平淡无奇，但配合幂运算的运算法则 a^(x+y) = a^x · a^y，就产生了化学反应：

a^13 = a^(8+4+1) = a^8 · a^4 · a^1

原本需要 12 次乘法的计算，现在只需要 3 次乘法加上若干次平方。更关键的是，a^1、a^2、a^4、a^8 这一串数可以通过不断对自己平方得到：a^2 = (a^1)^2，a^4 = (a^2)^2，a^8 = (a^4)^2。生成整条链条只需要 log2(n) 次平方，而选择哪些项相乘，取决于指数的二进制位是不是 1。

这就是二进制分解的全部魔力。它把一个"乘法次数与指数成正比"的问题，变成了"乘法次数与指数位数成正比"的问题。我习惯用一个生活化的类比来解释给新人听：你要搬 13 箱货，朴素做法是一箱一箱搬；快速幂的做法是先搞清楚 13 = 8 + 4 + 1，然后找到"一次搬 8 箱""一次搬 4 箱""一次搬 1 箱"的三种搬法，组合起来用三次搞定。前提是你得知道怎么凑出 8、4、1——也就是怎么生成那串平方链。

1.3 递归写法和迭代写法，到底该选哪个

快速幂有两种主流写法，思路完全一致但形态不同。递归版的逻辑是：a^n = (a^(n/2))^2 （n 为偶数），a^n = (a^(n/2))^2 · a （n 为奇数）。代码短得像数学公式，可读性极好，是教学时的首选。

def pow_recursive(base, exp): if exp == 0: return 1 half = pow_recursive(base, exp // 2) if exp % 2 == 0: return half * half else: return half * half * base

迭代版则是从低位往高位扫描指数的二进制位，维护一个"当前位的权值"（也就是 a^(2^i)），遇到 1 就把权值乘进答案：

def pow_iterative(base, exp): result = 1 while exp > 0: if exp & 1: result *= base base *= base exp >>= 1 return result

两者复杂度都是 O(log n)，理论性能一致。但实测下来迭代版通常更快，原因有两个：一是没有函数调用开销，递归版虽然有 log n 层，每层都是一次真实的函数调用；二是不消耗调用栈，递归深度在 n 极大时虽然也只有 60 层左右不算危险，但在某些嵌入式或受限环境里，能省则省。我在实际项目里一律用迭代版，递归版只在给新人讲原理时写一遍。这个选择没什么争议，除非你所在的语言对递归有特别的优化。

2. 把指数摊开来看：二进制分解的每一步在做什么

2.1 指数的每一位对应一次平方

理解迭代版快速幂，关键在于看懂循环体里那两个动作的分工。base *= base这一句是在"升级权值"，或者说是在准备下一位要用的底数；if exp & 1: result *= base这一句是在"决定要不要收下这个权值"。

把它们和二进制展开对应起来就很清楚了。假设指数是 13，二进制 1101。循环第 0 轮，exp 的最低位是 1，此时 base 里存的是 a^1，收下，result 变成 a^1；然后 base 平方成 a^2，exp 右移一位变成 6。第 1 轮，6 的最低位是 0，不收；base 平方成 a^4，exp 变成 3。第 2 轮，3 的最低位是 1，收下 a^4，result 变成 a^5；base 平方成 a^8，exp 变成 1。第 3 轮，最低位是 1，收下 a^8，result 变成 a^13；exp 变成 0，循环结束。

注意一个容易忽略的细节：base 的平方操作是无条件执行的，不管当前位是不是 1。因为权值的链条 a^1 → a^2 → a^4 → a^8 必须一直往上走，哪怕这一位用不上，下一位可能就用上了。这条链就是二进制的"位权"，和十进制里个位、十位、百位的道理一模一样，只不过这里的位权是 2 的幂而不是 10 的幂。

2.2 从高位扫和从低位扫，两种方向的取舍

除了从低位往高位扫，还有另一种写法是从高位往低位扫。这种写法的逻辑是：从左到右读二进制位，每读一位就把当前答案平方一次（相当于把已有的指数整体乘 2），如果这一位是 1，再额外乘一次 a。

def pow_high_to_low(base, exp): result = 1 # 先找到最高位的 1 for i in range(exp.bit_length() - 1, -1, -1): result *= result if (exp >> i) & 1: result *= base return result

两种写法的乘法次数几乎相同，都是从低位扫略快一点点，因为高位扫需要先确定位数。但高位扫有一个独特优势：它在构造答案的过程中，result 始终保持"已经处理的前缀位所对应的幂"，这在某些需要中途读取中间结果的场景下很有用，比如在十进制快速幂或者需要记录路径的问题里。我个人的习惯还是低位扫描，代码更紧凑，循环条件更自然。

顺带提一句，Python 里int.bit_length()是个很好用的内置方法，能直接拿到二进制的有效位数，比手动算 log 安全得多——用math.log2处理大整数会因为浮点精度出问题，这个坑我见过不止一个人踩。

2.3 手工推演：算一遍 3 的 13 次方

光看代码容易产生"我懂了"的错觉，真正手推一遍才能暴露理解漏洞。我们算 3^13，不取模，纯看过程。

指数 13 = 1101（二进制）。准备变量：result = 1，base = 3，exp = 13。

第一轮：exp = 13，最低位 13 & 1 = 1，收下，result = 1 × 3 = 3。base 平方变成 9。exp 右移变成 6。 第二轮：exp = 6，6 & 1 = 0，不收，result 保持 3。base 平方变成 81。exp 变成 3。 第三轮：exp = 3，3 & 1 = 1，收下，result = 3 × 81 = 243。base 平方变成 6561。exp 变成 1。 第四轮：exp = 1，1 & 1 = 1，收下，result = 243 × 6561 = 1594323。base 平方变成 43046721。exp 变成 0。 循环结束，结果 1594323。

验算：3^13 = 3^10 × 3^3 = 59049 × 27 = 1594323。对上了。整个过程只用了 4 次平方和 3 次乘法，一共 7 次乘法，而朴素算法需要 12 次。指数越大，这个差距越夸张。

2.4 取模为什么必须边算边取，而不是最后取一次

很多人第一反应是"最后再取一次模不就行了"，在小数据上确实看不出问题，但只要指数稍微大一点，中间结果就会膨胀到天文数字。Python 有任意精度整数还能扛，C++/Java 里 long long 只有 64 位，大约 1.8 × 10^19，a^13 这种量级就已经接近上限了，再大就直接溢出，而你最后取模取出来的是溢出后的垃圾值，返回结果完全错误却不会报错。

正确做法是全程取模。依据是同余运算的性质：(a × b) mod m = ((a mod m) × (b mod m)) mod m。这条性质保证了每做一次乘法就取一次模，和最后统一取模的结果完全一致。所以标准写法里，每一次result = result * base % mod和base = base * base % mod都要带取模。

long long fast_pow(long long base, long long exp, long long mod) { long long result = 1 % mod; base %= mod; while (exp > 0) { if (exp & 1) result = result * base % mod; base = base * base % mod; exp >>= 1; } return result; }

这里有两个容易写错的点。第一，result初始化成1 % mod而不是直接1，因为当 mod = 1 时，正确答案是 0，直接写 1 会返回错误结果。第二，入口处base %= mod，防止传进来的 base 本身就超过 mod，虽然第一步乘法后取模也能纠正，但一开始就规整能让中间值更可控。

3. 取模快速幂的边界与陷阱：教程里不会写的那部分

3.1 当模数逼近 long long 上限，乘法真的会溢出

上面那段 C++ 代码看起来很完美，但它在一种情况下会悄悄出错：mod 大于约 3 × 10^9 时。原因在于result * base的两个操作数都是小于 mod 的数，乘积最大可以接近 mod^2。如果 mod 是 10^18 这个量级，mod^2 就是 10^36，远远超过 long long 的 9.2 × 10^18 上限，直接溢出成负数或者随机值。

这个坑特别阴险，因为溢出不报错，你的函数照样返回一个数，只是答案是错的。我在一个需要处理 10^18 级模数的项目里被这个坑咬过一次，排查了大半天，最后是通过把中间结果打印出来和 Python 对照才发现的。

解决办法分三档，按场景选择：

第一档，模数不超过 2 × 10^9 左右时（保证 mod^2 < 2^63），直接用 long long 乘法，没有任何问题，这是绝大多数算法题的情况。

第二档，支持__int128的编译器（GCC 系），直接把乘法提升到 128 位，取模后再转回来，简单粗暴且几乎零成本：

long long mul_mod(long long a, long long b, long long mod) { return (long long)((__int128)a * b % mod); }

第三档，编译器不支持 128 位整数，那就得手写"龟速乘"。

3.2 龟速乘：用时间换安全的乘法

龟速乘（也叫快速乘）的思路和快速幂一模一样，只不过它做的是加法而不是乘法——把 a × b 拆成若干个 a 相加，同样用二进制分解把加法次数压到 log 级：

long long mul_mod(long long a, long long b, long long mod) { long long res = 0; a %= mod; while (b > 0) { if (b & 1) res = (res + a) % mod; a = (a + a) % mod; b >>= 1; } return res; }

复杂度从乘法的 O(1) 变成了 O(log b)，整个快速幂的复杂度因此从 O(log n) 变成 O(log^2 n)。听起来很亏，但在模数极大且编译器不支持 128 位的场景下，这是唯一安全的选择。60 × 60 = 3600 次加法对现代机器来说仍然是瞬间，安全性远比那点性能重要。

提示：如果你的平台是 Clang 或 GCC，优先用__int128；MSVC 不支持这个类型，需要换成_umul128或者自己写龟速乘。跨平台代码里建议做一个条件编译的封装，别在业务代码里到处写__int128。

3.3 那些必须单独处理的边界条件

边界值是快速幂最容易翻车的地方，我整理了几个必须显式处理的情况。

exp = 0 的情况值得多说一句。数学上任何非零数的 0 次方都是 1，0 的 0 次方在算法语境下通常也约定为 1。但如果 mod = 1，答案必须是 0，因为所有数对 1 取模都是 0。写1 % mod一行就同时覆盖了这两种情况，比写分支判断优雅。

exp 为负的情况是很多人以为不会遇到、结果遇到的。快速幂本身只处理非负指数，负指数必须转化为base^exp = (base^-1)^(-exp)，也就是先求 base 在模 mod 下的乘法逆元。这一步的前提是 base 和 mod 互质，否则逆元不存在，整个表达式在整数模意义下没有定义。代码里如果没做这个判断，遇到不互质的情况会算出错误答案而不自知。

3.4 费马小定理与逆元的快速求法

说到逆元，就绕不开费马小定理。它的内容是：如果 p 是素数，且 a 不是 p 的倍数，那么 a^(p-1) ≡ 1 (mod p)。两边同乘 a^(-1)，得到 a^(p-2) ≡ a^(-1) (mod p)。

这意味着在模素数 p 的意义下求逆元，只需要调用一次快速幂算 a^(p-2) mod p。这个结论在算法题里的出现频率极高，几乎成了套路：

long long mod_inverse(long long a, long long p) { return fast_pow(a, p - 2, p); }

但用之前必须确认两个条件：p 是素数、a 不是 p 的倍数。这两条缺一不可。我曾经见过有人在一个模数是合数的题目里套这个公式，结果答案错误还找不到原因，最后发现是没验证素数条件。

模数不是素数时，就得用扩展欧几里得算法解 a·x + p·y = gcd(a, p) = 1 得到 x，或者用欧拉定理把指数换成 φ(p) - 1。扩展欧几里得的写法不长，但需要理解裴蜀定理，这里不展开，只提醒一句：先判断 gcd(a, p) 是不是 1，不是 1 的话逆元根本不存在，任何公式都救不了。

4. 矩阵快速幂：把线性递推从 O(n) 压进 O(log n)

4.1 为什么线性递推天然适合矩阵

快速幂能处理的不只是数的幂，只要一个运算满足结合律，并且能定义出"单位元"，这套二进制分解的框架就能搬过去。矩阵乘法满足结合律，单位元是单位矩阵，所以矩阵也能做快速幂。这个推广本身不稀奇，稀奇的是它恰好能解决一大类问题：线性递推。

考虑斐波那契数列 F(n) = F(n-1) + F(n-2)。朴素递推要算第 n 项就得迭代 n 次，n 到 10^18 时同样跑不动。但如果把相邻两项打包成一个列向量 [F(n), F(n-1)]^T，那么从 [F(n-1), F(n-2)]^T 到它的转换就是一个固定的线性变换：

[F(n) ] [1 1] [F(n-1)] [F(n-1)] = [1 0] · [F(n-2)]

这个 2×2 矩阵就是所谓的转移矩阵。既然每一步转移都是乘同一个矩阵 M，那么 n 步之后就是 M^n 作用于初始向量。求 M^n 用矩阵快速幂，复杂度 O(k^3 log n)，其中 k 是矩阵阶数。对于 k = 2 的斐波那契，就是 8 log n 次乘法，n = 10^18 时大约 480 次，瞬间完成。

我特别喜欢用一个类比来描述这件事：朴素递推像是每天走一步，要走十亿天；矩阵快速幂像是发现"每走一步的动作完全一样"，于是把"走一步"这个动作打包成一个变换，直接算"走十亿步"这个变换本身长什么样。变换的复合是结合的，所以能二分。

4.2 转移矩阵怎么构造：从状态向量出发

构造转移矩阵有一套固定流程，掌握之后几乎所有线性递推都能套。

第一步，确定状态向量。它必须包含足以推出下一项的全部信息。斐波那契只需要前两项，所以状态是 [F(n), F(n-1)]。如果是三阶递推 F(n) = aF(n-1) + bF(n-2) + cF(n-3)，状态就是 [F(n), F(n-1), F(n-2)]，维度是 3。

第二步，写出从当前状态到下一状态的线性方程组。以斐波那契为例，下一状态是 [F(n+1), F(n)]，其中 F(n+1) = 1·F(n) + 1·F(n-1)，F(n) = 1·F(n) + 0·F(n-1)。把系数按行排列，就得到上面那个矩阵。

第三步，确认初始向量。斐波那契取 [F(1), F(0)] = [1, 0] 或者 [F(2), F(1)] = [1, 1]，取决于你的下标定义。这一步最容易出错，因为差一位就全错了，实际写的时候务必用小数据验证前几项。

有个更通用的技巧是直接构造一个形如 [[a, b], [1, 0]] 的矩阵，第一行填递推系数，第二行是"移位"用的单位行。这个模式对任意二阶线性递推都成立，不用每次重新推。

4.3 矩阵快速幂的代码骨架与单位矩阵

矩阵版的快速幂和标量版的结构完全一致，只是把乘法换成了矩阵乘法，把 1 换成了单位矩阵：

const int N = 2; long long mod; struct Matrix { long long m[N][N]; Matrix() { memset(m, 0, sizeof(m)); } }; Matrix multiply(const Matrix &a, const Matrix &b) { Matrix c; for (int i = 0; i < N; i++) for (int k = 0; k < N; k++) { if (a.m[i][k] == 0) continue; for (int j = 0; j < N; j++) c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod; } return c; } Matrix mat_pow(Matrix base, long long exp) { Matrix result; for (int i = 0; i < N; i++) result.m[i][i] = 1; // 单位矩阵 while (exp > 0) { if (exp & 1) result = multiply(result, base); base = multiply(base, base); exp >>= 1; } return result; }

这里有个我见过很多人写错的地方：单位矩阵的主对角线元素要设成 1 % mod，不是 1。道理和标量版一样，mod = 1 时单位矩阵其实是零矩阵。虽然这种极端情况不常见，但写对了不费事。

另一个细节是循环顺序。上面用的是 i-k-j 而不是标准的 i-j-k，原因是在a.m[i][k] == 0时可以直接跳过整个内层循环，稀疏矩阵下能省不少时间。同时把累加放在最内层，让 c[i][j] 在寄存器里反复累加，减少内存写入次数，实测在 N 较大时能快 20% 到 30%。

4.4 带常数项、带求和项的递推怎么塞进去

现实中的递推往往没这么干净。比如 F(n) = F(n-1) + F(n-2) + 5，多了一个常数项。常数项不参与线性组合，看起来破坏了矩阵结构，解决办法是给状态向量加一维常数，恒为 1。

状态从 [F(n), F(n-1)] 变成 [F(n), F(n-1), 1]，转移矩阵变成 3×3：

[1 1 5] [1 0 0] [0 0 1]

最后一行 [0 0 1] 保证常数 1 在转移后还是 1，而第一行第三列的 5 就是把常数项加进去的位置。这个"加一维常数"的模式可以无限套用，有几个常数项就加几维。

更复杂的是带求和的情况，比如要求 S(n) = F(1) + F(2) + ... + F(n)。这时候需要把 S(n) 也放进状态向量。因为 S(n) = S(n-1) + F(n)，而 F(n) 能由前两项表示，所以状态可以写成 [F(n), F(n-1), S(n)]，转移矩阵相应变成 3×3：

[1 1 0] [1 0 0] [1 1 1]

第三行 [1 1 1] 表达的是 S(n+1) = S(n) + F(n+1) = S(n) + F(n) + F(n-1)。用这种方式，前缀和问题也能 O(log n) 解决。

我踩过的一个坑是：状态向量的顺序必须和转移矩阵的列顺序严格对应，一旦搞乱，矩阵看起来"差不多对"但结果就是错的。我的习惯是写代码前先在纸上把状态向量和每一行方程写清楚，标注好索引，再翻译成代码。省下来的调试时间远超写纸的那两分钟。

4.5 矩阵乘法的常数优化

矩阵快速幂的复杂度是 O(k^3 log n)，k 是矩阵维度。k 小的时候没什么可优化的，但 k 到 100 甚至 200 时，常数因子就很要命了。几个实测有效的技巧：

一是延迟取模。不要每加一次就取模，而是用 long long 暂存，等累加到快溢出时再统一取模。具体阈值可以按2^63 / (max_element^2)估算，粗略地每次加完检查一次就行。这个改动通常能省 30% 以上时间。

二是跳过零元。矩阵在快速幂的早期往往很稀疏，if (a.m[i][k] == 0) continue;这一行在稀疏情况下收益很大。

三是循环顺序 i-k-j，前面已经说过，利用缓存局部性。

四是固定维度用模板或者宏，让编译器能展开循环、把数组放在栈上。用vector<vector<long long>>动态分配在 k 较小时反而更慢，因为每次乘法都在堆上跳来跳去。

5. 快速幂的几种变形，考场上和项目里都遇得到

5.1 指数大到读不进来：字符串指数与降幂

有些题目的指数不是整数，而是一个几百位的十进制字符串。直接读成 int 会溢出，用大整数库又太慢。两种处理路径。

第一种是十进制快速幂。仿照二进制分解，把指数按十进制位拆开：a^123 = ((a^1)^10 · a^2)^10 · a^3。每处理一位要做一次"十次方"（也就是连续平方三次再组合，或者直接用一个 precomputed 的 10 次幂函数），复杂度 O(len · log 10)，实际就是 O(len)。

第二种是欧拉降幂。核心是扩展欧拉定理：当 b ≥ φ(m) 时，a^b ≡ a^(b mod φ(m) + φ(m)) (mod m)，其中 φ 是欧拉函数。这样只需要在读取字符串的过程中对 φ(m) 取模，把指数压缩到 φ(m) 以内，再跑普通快速幂。

def read_exp_mod(s, phi): # 返回 (b mod phi, b 是否 >= phi) val = 0 big = False for ch in s: val = val * 10 + int(ch) if val >= phi: big = True val %= phi return val, big

注意那个big标记，它记录的是"原始指数是否已经超过 φ(m)"，直接决定要不要加 φ(m)。很多人只取模不加 φ(m)，在 b < φ(m) 时偶尔能蒙对，b 大了就全错。

5.2 等比数列求和：分治和矩阵两条路

求 1 + a + a^2 + ... + a^n 也是经典问题。n 大时逐项加不现实，可以用分治：

定义 S(n) = 1 + a + ... + a^n。当 n 为偶数时，S(n) = S(n/2) · (1 + a^(n/2+1))；奇数时类似处理。每次递归调用一次快速幂，总复杂度 O(log^2 n)。

另一条路是矩阵：把 [S(n), a^n] 作为状态，构造转移矩阵，一次矩阵快速幂 O(log n)。两条路都能用，分治写起来更直观，矩阵更快但需要构造。我在刷题时偏好分治，因为不容易构造错；性能敏感的场景用矩阵。

5.3 幂塔问题：指数本身也是幂

a^(b^c) 这种幂塔，指数部分是 b^c，先算出来再算外层。但 b^c 本身可能巨大，必须先降幂。用扩展欧拉定理递归处理，每层对 φ 取一次模，φ 会快速下降（一般 log 次后就到 1），所以总复杂度可控。

这个问题的坑在于 φ 的递归层数：每次取 φ 至少减半，所以最多 log m 层，不用担心栈溢出。但边界要小心，当模数降到 1 时，任何数对 1 取模都是 0，而 0 次方的约定又要单独处理，代码里一堆 if 是免不了的。

5.4 判断是不是完全平方数：二分加快速幂的组合

有一类题是判断 a^b 是不是完全平方数，b 巨大。直接算是算不出来的，思路是分析：如果 a 是完全平方数，那 a^b 一定是；如果 a 不是，那就要看 b 的奇偶性。这类题的分析过程比代码本身更重要，也是快速幂作为工具出现的典型场景——工具本身简单，难的是把它放在合适的位置。

6. 踩坑实录：一次真实的 TLE 排查

6.1 现象与初步怀疑

那次的情况是这样的：一个统计类的接口，需要计算若干组合数并对一个大素数取模，每次都要调用快速幂求阶乘的逆元。数据量不大，理论上几百次调用就该结束，但实际跑了几秒还没返回。

第一反应是快速幂写错了，检查代码，逻辑看起来完全正确。第二反应是 mod 太大导致乘法溢出——把 mod 换成小值测试，速度立刻正常。到这里基本锁定：不是算法复杂度的问题，是乘法运算本身出了问题。

6.2 定位：溢出导致的隐式开销

进一步检查发现，mod 接近 10^18，而代码里用的是long long直接相乘。虽然大部分情况下不会溢出（因为随机数相乘超过 9.2×10^18 的概率不算高），但一旦溢出成负数，后面的取模运算在 C++ 里对负数有特殊处理，结果不符合预期。更麻烦的是这不会导致崩溃，只会让结果变成一个奇怪的数，然后在后续运算里引发更多的连锁错误。

改成__int128之后，问题立刻消失。整个过程算下来，从怀疑算法到定位到溢出花了大约四十分钟，其中大部分时间花在"算法逻辑看起来没问题"的自我怀疑上。

6.3 教训：先验证数据范围，再怀疑算法

这次之后我形成了一个习惯：拿到任何涉及取模的代码，第一件事是确认mod * mod会不会溢出当前类型。一个简单的判断表：

这个表贴在显示器旁边好几年了，省下的调试时间无法统计。特别是int那一行，46340 这个数字远小于很多人的直觉，用 int 做模运算在 mod 稍大时就会翻车。

6.4 递归与迭代的实测差距

顺手做个对比。在同一个平台上跑 10^6 次指数为 10^18 的快速幂，迭代版耗时约 0.42 秒，递归版约 0.58 秒，差距接近 40%。这个差距在单次调用时可以忽略，但在循环里调用十万次时就变成了秒级的差异。

递归版慢的原因主要是函数调用本身的开销，以及编译器对递归的优化程度不如对循环。另外递归版在栈空间紧张的环境里有风险，虽然 60 层深度不算什么，但如果指数是几百位的大整数，深度会相应增加。

7. 快速幂在真实工程里的落点

7.1 密码学协议中的模幂运算

现代密码学里大量依赖模幂运算，虽然具体算法的细节不便展开，但从数学形式上看，核心操作就是算 g^x mod p，其中 x 可能是一个几百位的私钥。这个计算必须足够快，否则整个握手流程会被拖垮。快速幂在这里是不可替代的基础设施，而且往往还会配合窗口法（windowed exponentiation）进一步优化——一次处理多个二进制位，预计算幂次表，把乘法次数再降一截。

我参与过一个需要频繁做密钥协商的内部模块，性能瓶颈最后就落在模幂上。把朴素的二进制快速幂换成 4 位窗口法之后，吞吐量提升了接近 30%，这个收益在服务器端是相当可观的。

7.2 滚动哈希里的幂预处理

字符串匹配里常用的滚动哈希，本质是把字符串看成一个 base 进制的数，然后对一个大素数取模。计算子串哈希时需要 base 的幂，如果每次现算，复杂度会退化。标准做法是预处理一个幂数组 pw[i] = base^i mod mod，而这个数组的生成用的就是快速幂（或者是递推，两者结果一致但递推更快）。

这里的坑在于 base 的选择。base 太小容易碰撞，太大又容易溢出，一般选 131 或 13331，配合 10^9+7 或 10^9+9 这类模数。选完之后一定要用快速幂验证一下 base^(mod-1) mod mod 是不是 1，不是的话说明模数不是素数，整个哈希的数学基础就有问题。

7.3 图形变换的矩阵复合

计算机图形学里，平移、旋转、缩放都可以用矩阵表示。如果要把同一个变换重复应用很多次（比如分形图形的迭代生成、动画的关键帧插值），直接循环相乘的效率是 O(n·k^3)，而矩阵快速幂是 O(k^3 log n)。对于生成大规模分形图案这种场景，差距是分钟级和毫秒级的区别。

这里的状态矩阵通常是 3×3 或 4×4 的齐次坐标矩阵，维度不大，所以矩阵乘法的常数优化没那么重要，反倒是浮点误差的累积需要注意。快速幂把 log n 次乘法压缩到一起，误差不会比逐步相乘更大，甚至在 n 很大时反而更稳，因为中间结果的量级被控制住了。

7.4 组合计数与大指数

求 C(n, k) mod p 时，如果 p 是素数且 n 小于 p，标准做法是预处理阶乘和阶乘逆元，逆元用快速幂求。这条路在竞赛和实际业务里都用得极多，比如计算概率、统计方案数、做公平的随机分配。

一个容易忽略的点是当 n 大于等于 p 时，阶乘里会含有 p 的因子，直接算逆元会失效（阶乘 mod p 等于 0，0 没有逆元）。这时需要用 Lucas 定理分治。我见过不少人在数据范围没看清的情况下套公式，结果在小数据上全对、大数据上全错，排查起来非常痛苦。

8. 我个人在用快速幂时的几条固定习惯

写到这里，把这么多年沉淀下来的几个习惯分享一下，都是踩坑换来的。

第一，永远先写边界测试。exp=0、mod=1、base=0 这三组输入写完代码立刻测，通过之后再测常规数据。这三组覆盖了 80% 的边界错误。

第二，模数超过 10^9 就用 128 位或者龟速乘，不要心存侥幸。溢出不报错，这是最可怕的错误类型。

第三，矩阵快速幂先在纸上推前五项。构造完转移矩阵，手算前五项和暴力递推对照，对上了再写代码。矩阵错一位，调试成本极高。

第四，递归版只在教学场景用。实际代码一律迭代，性能好、无栈风险、跨语言移植一致。

最后分享一个我最近才意识到的细节：Python 的pow(base, exp, mod)内置函数就是快速幂的 C 实现，速度比手写 Python 循环快几十倍。在 Python 项目里除非你要做矩阵快速幂或者有特殊需求，直接用内置的pow三参数版本就行，没必要自己造轮子。这个函数还很贴心地处理了负指数（自动转逆元，Python 3.8+），边界条件全帮你兜住了。知道什么时候不用自己写，也是一种经验。