企业官网建设流程全解析

看到“快速幂”这三个字的时候，我猜很多备战CSP-S的同学第一反应是：这不就是一个简单的模板吗，背下来不就行了？但说实话，快速幂在提高组的考法远不止“套模板”这么简单。它是数论、组合数学、矩阵优化、递推加速的公共地基，光是最近两三年的初赛和复赛题目里，快速幂穿的马甲就已经换了好几套——有时候藏在求逆元里，有时候躲在递推优化里，还有时候化成一个巨大的指数让你用费马小定理先压一轮再动手。

这篇咱们就把快速幂彻底聊透。从它到底为什么快讲起，到递归、迭代、位运算三个常用实现，再到CSP-S真正会碰到的几个实战场景，连容易翻车的溢出、取模、边界条件一起盘一遍。不管你是刚开始学提高组算法，还是复赛前想快速过一遍模板，这篇都能给你省下不少时间。

1. 快速幂到底在解决什么问题

先说最朴素的需求。如果让你计算 (a^b)，直接从1开始连乘 (b) 次，当然能得到结果。但问题在于，竞赛题里的指数 (b) 经常是 (10^9) 甚至 (10^{18}) 这个量级的，一些题目还会加上一个取模限制，让你求 (a^b \bmod p)。连乘基本等于直接把一个 (O(b)) 的复杂度压在程序身上，而比赛评测机通常只给你一秒，csp-s一共也就几道题，单题肯定是跑不过的。

既然乘的规模太大，那就得想办法把指数变小。快速幂的核心思路就是幂次的二进制拆分，本质上是一种分治思想的特化版本。比如要算 (3^{13})，13的二进制是1101，所以 (13 = 8 + 4 + 0 + 1)，于是 (3^{13}) 就能拆成 (3^8 \times 3^4 \times 3^1)，而不是老老实实乘13个3。这样一算，原本要13次乘法，现在只需要先不断平方得到 (3^1, 3^2, 3^4, 3^8)，再把需要的几个二进制位对应的幂乘到一起，整个过程的乘法次数是从 (O(b)) 的指数级运算直接降到了 (O(\log b))。

遇到这种幂运算加取模的题目，比如 (a^b \bmod p) 里 (b) 是 (10^{18})，log 一下也就60多次递归或循环，这个差距是肉眼可见的。CSP-S初赛里经常考复杂度分析，一看到计算幂的代码让你判断时间复杂度，答案基本都会落在 (O(\log b))。复赛就更直接了，很多题不会明说“这题考快速幂”，但你在优化递推或者处理大数取模的时候绕不开它。

还有一点容易被忽略：快速幂不只是算整数幂，它最值钱的地方在于“幂运算的逻辑可以抽象出来”。只要能定义好“乘法”和“单位元”的矩阵快速幂，能解决一大批递推问题，这个我们后面第4节详细说。

一句话总结这一节——快速幂解决的是重复乘法的规模爆炸问题。只要运算满足结合律，就能用这个思路加速，这也是它在竞赛里地位这么高的原因。

2. 核心原理拆解：二进制拆解与分治思想

快速幂的原理，说白了就是把指数“看成二进制”，然后利用平方把幂次一步步翻倍，实现“幂次翻倍、底数平方”的同步跳转。

拿 (2^{10}) 来举例子。10的二进制是1010，从最低位开始看：

• 第0位是0，说明结果不需要乘 (2^{1})；
• 第1位是1，说明结果要乘 (2^{2})；
• 第2位是0，不需要 (2^{4})；
• 第3位是1，需要乘 (2^{8})。

但等一下，程序不可能一开始就知道 (2^8) 是多少。所以实际的做法是：让底数不断自乘，也就是每处理一位二进制，底数就变成原来的平方。这样当循环走到第3位时，底数已经变成了 (2^{8}) 了，直接取用就行。

如果你学过递归，快速幂还有另一种理解方式。利用数学上的拆分：

[ a^b = \begin{cases} (a^{b/2})^2 & \text{b为偶数} \ (a^{b/2})^2 \times a & \text{b为奇数} \end{cases} ]

每一步把问题规模砍半，递归深度也是 (O(\log b))。两个实现思路其实是同一个数学本质，只不过一个用循环展开了递归栈，一个直接递归而已。

既然原理讲清了，咱们再算一笔账。假设 (b = 10^9)，朴素做法要循环 (10^9) 次，而快速幂只需要不超过30次平方和乘法。这对那些评测数据给满的CSP-S题目来说，完全就是两种命运：一个是妥妥超时，一个是零压力通过。

这里有一个重要的前提：这个运算是需要满足结合律的。比如普通整数乘法和矩阵乘法都满足结合律，所以都能用快速幂；但如果你处理的对象运算不满足结合律，那就不能直接套模板，得先想想运算规则。

另外提醒一下，在处理“模意义下的快速幂”时，模运算是可以直接作用到乘法里的，因为同余关系满足：

[ (a \times b) \bmod p = ((a \bmod p) \times (b \bmod p)) \bmod p ]

这给了我们一个很大的便利：在快速幂循环中，每一步平方、每一步相乘，都可以先取模再做乘法，这样就算中间过程也不会炸掉数据范围。这个细节非常重要，我单独拆到下一节代码实现里展开讲。

3. C++实现：递归、迭代与位运算全解析

这部分直接上代码。我会给出三种常用写法，并附上每段的意图解释，方便你不仅会背模板，还是真正理解每一步在干嘛，题目稍微变形的时候才知道怎么调。

3.1 递归写法：最直观的理解方式

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll fast_pow(ll a, ll b, ll mod) { if (b == 0) return 1 % mod; // 任何数的0次幂都是1，注意模数可能为1 ll t = fast_pow(a, b >> 1, mod); // 先算一半幂的结果 t = t * t % mod; // 幂次翻倍 = 结果平方 if (b & 1) t = t * a % mod; // 如果是奇数，还要再乘一个底数 return t; }

这段代码是最好理解的，因为它是严格按照数学定义来的。每次把指数 (b) 除以2，等子问题返回后再平方，最后判断奇偶性决定要不要多乘一个底数。唯一要注意的是返回值那里写了1 % mod，这个是为了应对mod == 1的特殊情况。

递归写法的优点是思路清晰、不容易写错，缺点是多了函数调用开销。不过不要怕，因为快速幂的递归深度最多也就60层左右（对应 (10^{18}) 的指数），完全不会爆栈，性能损失也可以忽略。所以如果你是在赛场上追求稳定，递归版完全够用。

3.2 迭代写法：性价比最高的模板

ll fast_pow(ll a, ll b, ll mod) { ll res = 1 % mod; a %= mod; while (b > 0) { if (b & 1) res = res * a % mod; // 当前二进制位为1，就把当前a乘进去 a = a * a % mod; // a平方，对应二进制位左移一位 b >>= 1; // 检查下一位 } return res; }

这段代码和递归版是等价的，但是省去了函数调用，而且逻辑上更贴近“二进制拆解”的表达。我自己的习惯是赛场上写这个迭代版，因为不用考虑递归边界问题，调试起来也简单。

解释一下代码的核心位运算逻辑：

• if (b & 1)用来判断 b 的最后一位二进制是否为1。
• a = a * a % mod相当于让幂次翻倍，比如开始是 (a^1)，下一轮就是 (a^2)，再下一轮就是 (a^4)。
• b >>= 1把指数右移一位，相当于把处理过的最低位丢掉。

三个操作合在一起，循环次数就是b的二进制位数，也就是 (O(\log b))。这段代码是可以直接背下来的模板，而且背完一定得理解，后面所有扩展写法都是在这个基础上加东西。

3.3 大数相乘的溢出隐患

这里必须专门提一个很多新手会踩的大坑：就算你用了ll，乘法仍然会溢出。

C++里long long是有符号64位，范围大约是 (\pm 9.22 \times 10^{18})。而快速幂里的res * a和a * a在做模运算之前，这两个数的乘积很可能已经超过这个范围。假设 (mod) 是 (10^9+7)，res和a都可能接近这个值，两者相乘大概是 (10^{18}) 量级，刚好还在long long的屋檐下；但如果模数再大一点，比如接近 (10^{18})，那相乘就直接炸了。

有两个解决办法：

办法一：限制模数范围。CSP-S一般常用的1e9+7、1e9+9、998244353都是这个范围内的，用long long做乘法暂时安全。但如果你在写题解或者题目给了自定义超大模数，就需要谨慎。

办法二：使用__int128做中间乘法。

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

然后所有乘法都换成mul_mod调用。

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

这段代码我建议你直接收藏，遇到奇怪的模数时直接拿出来替换。(10^{18}) 乘以 (10^{18}) 用__int128刚好能存下，不会溢出。代价是__int128不是标准C++类型，部分编译器不支持（GCC和Clang支持，Visual Studio的MSVC不支持），但竞赛环境基本都支持，所以放心用。

4. 实战案例：三组CSP-S风格问题拆解

光会写模板不算会，得知道题目里怎么用。我选三个非常有代表性的场景，从易到难过一遍，每个场景都有完整的思路和代码。

4.1 案例一：纯模板题，(a^b \bmod p)

题目背景：输入三个正整数 (a, b, p)，求 (a^b \bmod p)。其中 (1 \le a, p \le 10^9)，(1 \le b \le 10^{18})。

这是快速幂最简单的考法，几乎就是纯模板，但也是初赛和复赛最常见的引子。

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll fast_pow(ll a, ll b, ll mod) { ll res = 1 % mod; a %= mod; while (b > 0) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } int main() { ll a, b, p; cin >> a >> b >> p; cout << fast_pow(a, b, p) << endl; return 0; }

这里有个小细节：a %= mod在一开始就要做，因为如果 (a) 比 (p) 大很多，直接拿原数据算再取模也能得到正确结果，但中间乘积容易变大，所以提前取模更稳妥。此外，res = 1 % mod也处理了 (mod = 1) 的情况，此时任何数模1结果都是0，1 % 1直接就是0，后面的循环就算白算，结果依然正确。

这种题别看简单，CSP-S初赛经常把它包装成“下列哪段代码能正确计算 (a^b \bmod p)”的选择题，选项里会故意把if (b & 1)写成if (b % 2 == 1)但忘了a = a * a % mod的位置，或者干脆把右移写成左移。所以模板不仅要会背，还要能在选项里一眼看出问题。

4.2 案例二：矩阵快速幂加速递推

如果说整数快速幂是基础，那矩阵快速幂就是CSP-S真正的常客。最经典的场景就是斐波那契数列优化。

题目背景：求斐波那契数列第 (n) 项对 (10^9+7) 取模，其中 (n \le 10^{18})。

斐波那契的递推公式是 (F_n = F_{n-1} + F_{n-2})，如果用循环从1算到 (n)，复杂度 (O(n))，(n) 一大就超时。但是我们可以把递推关系改写成矩阵形式：

[ \begin{bmatrix} F_{n} \ F_{n-1} \end{bmatrix}

\begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix} \times \begin{bmatrix} F_{n-1} \ F_{n-2} \end{bmatrix} ]

如果一直往前展开，就能得到：

[ \begin{bmatrix} F_{n} \ F_{n-1} \end{bmatrix}

\begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}^{n-1} \times \begin{bmatrix} F_{1} \ F_{0} \end{bmatrix} ]

这样就变成了求矩阵的 (n-1) 次幂，而矩阵乘法本身满足结合律，正好可以用快速幂，只是把“整数的相乘”换成“矩阵的相乘”。矩阵乘法是 (O(k^3))，快速幂部分是 (O(\log n))，合起来是 (O(k^3 \log n))，对于2x2矩阵来说就是 (O(8 \log n))，完全可行。

直接看代码：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1e9+7; struct Matrix { ll m[2][2]; Matrix() { memset(m, 0, sizeof(m)); } Matrix(ll a, ll b, ll c, ll d) { m[0][0] = a; m[0][1] = b; m[1][0] = c; m[1][1] = d; } }; Matrix mul(Matrix A, Matrix B) { Matrix C; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) C.m[i][j] = (C.m[i][j] + A.m[i][k] * B.m[k][j]) % MOD; return C; } Matrix mpow(Matrix base, ll n) { Matrix res(1, 0, 0, 1); // 单位矩阵 while (n > 0) { if (n & 1) res = mul(res, base); base = mul(base, base); n >>= 1; } return res; } int main() { ll n; cin >> n; if (n == 0) { cout << 0 << endl; return 0; } Matrix M(1, 1, 1, 0); Matrix ans = mpow(M, n - 1); cout << ans.m[0][0] << endl; // F(n) return 0; }

这个写法就是一种“抽象快速幂”的示范，注意两点。

第一，需要定义好“单位元”。在整数快速幂里，单位元是1，因为任何数乘1都等于自身；在矩阵快速幂里，单位元是单位矩阵，即对角线为1、其他为0的矩阵。没有单位元的话，初始化res就没有意义。

第二，矩阵乘法内部的取模操作一定要在加法之后做，不然多次累加也会溢出。这里C.m[i][j]每次累加前其实可以再对加数取一次模，但通常因为3个MOD相加也不超过3e9+21，在ll范围内是安全的。如果你遇到维度更大的矩阵，比如某些线性递推题目用到10x10矩阵，中间累加10个数也没问题。

矩阵快速幂能解决的问题远不止斐波那契，任何线性递推关系，只要你能写出形如“下一个状态 = 矩阵 × 当前状态”的公式，都可以用同样的板子加速。CSP-S的压轴题经常是递推加矩快，所以这个代码值得反复练到直接默写的程度。

4.3 案例三：等比数列求和的分治加速

题目背景：求 (1 + a + a^2 + \cdots + a^{n-1} \bmod p)，其中 (n \le 10^{18})。

如果直接用循环累加，又是 (O(n)) 超时。但如果只靠快速幂单点求值，也不能直接一次性求出和，因为求和是多个幂的累加。这个问题的经典解法是“分治 + 快速幂”的组合。

设 (S(n) = 1 + a + a^2 + \cdots + a^{n-1})，对 (n) 分奇偶讨论：

• 当 (n) 为偶数时： [ S(n) = S(n/2) + a^{n/2} \cdot S(n/2) = S(n/2) \cdot (1 + a^{n/2}) ] 这个式子的意思是，前一半的和，加上后一半每一项都乘以 (a^{n/2})，整体仍然是等比数列，可以直接提公因子。

• 当 (n) 为奇数时，最简单的是递归到 (n-1)，再把最后一项 (a^{n-1}) 单独加起来。

代码实现：

ll fast_pow(ll a, ll b, ll mod) { ll res = 1 % mod; a %= mod; while (b > 0) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } ll geo_sum(ll a, ll n, ll mod) { if (n == 0) return 0; if (n == 1) return 1 % mod; if (n % 2 == 0) { ll half = geo_sum(a, n / 2, mod); return half * (1 + fast_pow(a, n / 2, mod)) % mod; } else { return (geo_sum(a, n - 1, mod) + fast_pow(a, n - 1, mod)) % mod; } }

注意这个算法的复杂度是 (O(\log n)) 吗？很多人会有疑问，因为奇数分支会先递归到 (n-1)，看起来像是退化了。实际上不会，因为 (n-1) 是偶数，下一步就会除以2，所以总体递归深度还是 (O(\log n)) 级别，加上每次递归里调用一次快速幂是 (O(\log n))，总复杂度 (O(\log^2 n))。这个复杂度对于 CSP-S 的数据范围完全没问题。

这里再补充一个替代方案。如果模数 (p) 是质数，等比数列求和也可以直接用快速幂算出 (a^{n})，然后借助费马小定理求逆元得到：

[ S(n) = \frac{a^n - 1}{a - 1} \pmod p ]

但这样做有个前提：(a-1) 和模数互质，而且模数必须是质数才有逆元。如果模数是合数，逆元不一定存在，分治法就是更稳的选择。所以我的习惯是，通用做法用分治法，特定情况下可以用逆元公式快速出结果。

5. 竞赛中快速幂的常见错误与排查技巧

这部分是我自己踩过很多坑之后沉淀下来的自查清单。写代码的时候觉得都是对的，跑出来全错，十有八九是下面几个问题。

5.1 溢出问题没处理

我已经在前面详细说了，long long相乘可能溢出，尤其是模数接近 (10^{18}) 时。建议比赛前就把mul_mod写成__int128版本或者快速乘版本，平时做题就默认用这个，避免临场手忙脚乱。

5.2 取模的位置不对

快速幂里加法、乘法的取模时机非常重要，尤其是在矩阵快速幂里。矩阵乘法的三重循环里，累加结果一定要在加法之后、赋值字符串之前取模。如果你把取模放在A.m[i][k] * B.m[k][j]这一步之前，比如先对乘数取模，也是可以的，因为模运算对乘法有分配律，但放在累加完再取模是最简单的。

5.3 忽略了模数等于1的情况

如果模数等于1，结果永远是0。如果模板里写的res = 1 % mod而不是res = 1，能顺手处理这种情况。竞赛题虽然很少给模数为1的极端数据，但初赛的选择题会拿这个当陷阱。

5.4 递归深度过大或者边界条件写错

快速幂递归版本身的深度没问题，但是如果你扩展到了矩阵递归版本，随手可能多写一层，导致栈溢出。我建议迭代版为主，递归版只在快速验证时用。

5.5 指数为0的情况

任何非零数的0次幂都是1，0的0次幂在竞赛数学里通常约定为1。如果题目数据允许指数为0，你的模板返回1 % mod就是正确的。但要注意，底数为0、指数为0的组合，如果题目没有明确说明，建议加一个特判，避免歧义。

5.6 忘了对底数先取模

有时候 (a) 本身可能比 (p) 大得多，比如 (a = 10^{18})，(p = 10^9+7)，如果不先a %= mod，后面a = a * a % mod虽然也能得到正确结果，但在乘法瞬间a * a就会溢出。所以在进入循环前，一定要执行a %= mod。

排查建议：写完快速幂之后不要直接冲进去算大样例。先搞几个小数据，比如 (2^{10} = 1024)、(3^5 = 243)，再拿这几个结果和朴素循环的结果对比，确认无误后再测大样例。这种“暴力对拍”的方法能最快揪出模板问题。

为了帮你快速自查，我做了一张表格总结常见异常和对应的处理手段：

6. 从快速幂延伸出去：竞赛中的常见变体

前面说过，快速幂真正强大在“幂运算的逻辑可以被抽象”。除了矩阵快速幂，CSP-S里还有几个常见变体值得你提前了解，遇到了不至于发懵。

6.1 求逆元：费马小定理应用

如果模数 (p) 是质数，且 (a) 与 (p) 互质，那么根据费马小定理：

[ a^{p-1} \equiv 1 \pmod p ]

两边同时除以 (a)，得到：

[ a^{p-2} \equiv a^{-1} \pmod p ]

所以 (a) 的逆元就是 (a^{p-2} \bmod p)，这一步直接有快速幂完成。CSP-S里很多涉及“除法取模”的题，比如组合数取模、等比数列求和的通项公式，都需要先求逆元。快速幂在这里就是最底层的支撑工具。

还有一条很重要的知识链：如果题目要求模任意数 (p)（不一定是质数），那就需要用扩展欧几里得算法来求逆元，而不是费马小定理。我遇到过很多同学在合数模下直接用费马小定理，显然是错的。做题前一定先看模数是否为质数，这决定了逆元算法选型。

6.2 欧拉降幂处理超大指数

有些题目指数比 (10^{18}) 还大，甚至以字符串形式输入，比如 (a^{b} \bmod p)，其中 (b) 有100000位。直接快速幂是没法读完这么长的指数的。这时需要欧拉定理：

[ a^{\varphi(p)} \equiv 1 \pmod p \quad (gcd(a,p)=1) ]

其中 (\varphi(p)) 是欧拉函数。所以可以把巨大的指数先对 (\varphi(p)) 取模，再用快速幂计算。如果 (a) 和 (p) 不互质，还要对指数进行“加 (\varphi(p))”的处理，此处细节较多，等真正遇到时再单独展开。提这一嘴是为了让你明白，快速幂虽小，却是一切指数运算的最终执行者。

6.3 快速幂与组合数的结合

CSP-S提高组的排列组合题，一旦涉及模 (p)，基本都会要求计算阶乘、逆元、组合数。组合数公式：

[ C(n,k) = \frac{n!}{k!(n-k)!} \bmod p ]

需要预处理好阶乘数组，然后用快速幂求每个阶乘的逆元。这里再次用到了费马小定理加快速幂，属于高频组合拳。

6.4 相同基底的多点求值优化

有些题目要求同时计算 (a^{k_1}, a^{k_2}, \dots, a^{k_m}) 对同一个 (a) 做批量指数运算。一个优化思路是预处理 (a) 的 (2^0, 2^1, 2^2, \dots) 次幂数组，然后对每个指数只做二进制位拼接，相当于把每个查询从 (O(\log K)) 降到 (O(\text{popcount}(k)))，常数更小。虽然CSP-S直接这么考的次数不算多，但如果你在写进制哈希类题目，这个技巧能帮你省下不少时间。

7. 现场写题时的操作建议

最后聊一点偏赛场经验的东西。

我在模拟赛和正式赛里写快速幂，一般是这个固定流程：

1. 先想清楚题目是整数幂还是矩阵幂。如果是递推关系，先把递推矩阵写出来，不要直接硬套整数模板。
2. 确定模数，先判断是不是质数，决定后面能不能用费马小定理求逆元。
3. 写代码时带上mul_mod，不管模数多大，统一用__int128中转，省得检查半天。
4. 写完后跑三个自测数据：2^10 mod 100、3^5 mod 1（验证特殊边界）、123456789^1000000000 mod 1000000007（验证大指数）。如果这三个都过，基本就没问题。
5. 矩阵快速幂的话，自测用斐波那契数列，因为斐波那契的答案容易手算，比如第10项是55，第20项是6765。

第4步的第二个测试用例很多人会忽略，3^5 mod 1如果输出不是0，说明你的初始值没有处理1 % mod的情况。这种边界用例虽然极端，却是检验模板完整性的试金石。

另外，CSP-S复赛的评测机制对TLE和WA的判定是无情的，与其在写题时贪图“看起来快”的优化，不如先保证代码逻辑的绝对正确。快速幂代码量小，性能瓶颈也不在这一点微小的常数上，稳定比炫技重要得多。

还有个小技巧：矩阵快速幂的矩阵乘法，固定维度比如2x2，可以直接把三重循环展开写，能省下一点常数时间；维度大一点就别展开，循环结构更清晰，调试时也方便。

8. 写在最后的个人体会

快速幂这个算法，我第一次接触时也以为只是一个30行不到的模板，背下来万事大吉。直到后来做了一道递推题，用矩阵快速幂把 (n=10^{18}) 的数据轻松跑完，才真正意识到这玩意儿在竞赛体系里的分量有多重。它几乎横跨了初赛的复杂度分析、复赛的模板题、以及压轴题里的底层优化，属于“你会了不一定能拿高分，但不会一定吃亏”的知识点。

所以我的建议是：别满足于会写模板，最好能把这个算法的“拆指数二进制、同步平方、抽象幂运算”三个核心思想反复琢磨透。等你真正理解了它，很多看起来没什么关联的题目——数论、递推、组合数学、图论里的可达矩阵——都会在某个瞬间和你已经写过的快速幂模板产生连接，那种“原来都是同一个思路”的感觉，才是竞赛里最让人上瘾的瞬间。

后续如果时间允许，我可以再写一篇关于“欧拉降幂 + 扩展欧几里得求逆元”的专题，把模运算这个体系的最后几块拼图也补齐。当然，那篇的难度会再上一个台阶，适合已经把快速幂和矩阵快速幂吃透的同学继续追更。