C++快速幂完整实战讲解

C++快速幂完整实战讲解

1. 背景与意义

指数运算（a^n）是数学与计算机科学中最常见的操作之一。直观的计算方法是把基数a乘n次，但是当n很大（如数十亿、上亿甚至 10¹⁸）时，线性循环的时间复杂度O(n)将无法接受。为此，快速幂（又名“左移右乘”或 “指数平方法”）提供了一种将时间复杂度降低到O(log n)的技术。

在多数算法竞赛、密码学、数论与线性代数等领域，快速幂往往是必备技术。例如：

• 计算模幂 (pow_mod) 用于朴素加密/解密、RSA 中的大数运算；
• 计算阶乘模幂用来实现C(n, k)的快速求法；
• 解决a^b % m的竞赛题目；
• 计算矩阵平方幂实现快速求斐波那契数、线性递推等。

因为其运算简单、代码可读性高、且兼容几乎所有编程语言，快速幂已成为电脑学者的标配技巧。

2. 快速幂的核心思想

快速幂基于以下拆解公式：

an={an/2×an/2如果 n 是偶数an−1×a如果 n 是奇数an={an/2×an/2an−1×a​如果 n 是偶数如果 n 是奇数​

可进一步写成：

an=an/2×an/2若 n 为偶(a(n−1)/2×a(n−1)/2)×a若 n 为奇an=an/2×an/2(a(n−1)/2×a(n−1)/2)×a​若 n 为偶若 n 为奇​

这个拆分利用了二进制的特性：从高位到低位逐步处理指数二进制位。具体实现有两大变体：

1. 递归实现：直接按上面公式递归求解；
2. 迭代实现：利用指数的最低有效位，累积结果，同时把指数右移一位（n >>= 1），把基数平方。

两种实现都在O(log n)的时间复杂度内完成指数运算。

3. 递归实现

3.1 基本代码

long long powerRec(long long a, long long n) { if (n == 0) return 1; // 任何数的 0 次方为 1 long long half = powerRec(a, n >> 1); if (n & 1) // 奇数 return half * half * a; else // 偶数 return half * half; }

3.2 关键点解读

• n == 0为递归终止条件。
• n >> 1相当于n / 2，位运算比除法快。
• n & 1判断n是否为奇数。
• 递归深度最多⌊log₂ n⌋ + 1，对n < 10^18的情况，只需不到 64 层递归。这在大多数现代编译器下完全安全（递归深度通常 1e5 或更高）。

3.3 递归背后的数值问题

• 整数溢出：half * half * a可能产生 64 位溢出。若仅需要在不取模的情况下求伪值，使用__int128或long double可缓解；若已知需要取模，可将half与a先模，以保证中间结果不大。
• 无负指数：上面代码仅适用于n ≥ 0。若想支持负指数，需要使用浮点数或将题目转成求分数的形式。

4. 迭代实现

迭代实现是快速幂中最常用的形式，代码更简洁，递归带来的函数调用开销也消失。

long long powerIter(long long a, long long n) { long long result = 1; while (n > 0) { if (n & 1) // 当前最低位为 1 result *= a; // 乘以对应的基数 a *= a; // 基数平方 n >>= 1; // 移除最低位 } return result; }

4.1 迭代不需要递归

• 空间复杂度：常量 O(1)。
• 时间复杂度：同递归，为O(log n)。
• 可读性：大多数程序员更倾向于迭代版本，易于在代码审查时定位错误。

4.2 迭代与递归的比较

在极端大数（如n > 10^9）的情况下，递归方式完全无问题；但如果你在嵌入式或最小化内存场景，迭代更稳妥。

5. 取模实现（模幂）

当我们需要求a^n mod m（特别是m为 10⁹+7 等 32 位或 64 位素数）时, 直接做half * half计算会溢出。我们可以在每一步都做模运算，保证中间值不会太大。

long long modpow(long long a, long long n, long long mod) { long long result = 1 % mod; a %= mod; while (n > 0) { if (n & 1) result = (__int128)result * a % mod; // __int128 防止 64 位乘溢出 a = (__int128)a * a % mod; n >>= 1; } return result; }

5.1 关键技巧

1. 使用__int128：当a与mod都接近 10¹⁸ 时，a * a会溢出 64 位。__int128（若编译器支持）可以安全处理 128 位整数。
2. 按位取模：a %= mod先对基数做模，随后所有乘法保持在[0, mod)范围内，避免乘溢出。
3. 取模的顺序：一定先做乘，再做取模，而不是先取模后再乘。

5.2 典型应用场景

6. 栈与缓存：优化可读性与性能

6.1 将模幂抽成函数模板

在多语言项目中，模幂经常被多处调用。使用模板可以让编译器生成类型安全的代码。

template<typename T, typename U> T modpow(T a, U n, T mod) { T res = 1 % mod, base = a % mod; while (n > 0) { if (n & 1) res = (__int128)res * base % mod; base = (__int128)base * base % mod; n >>= 1; } return res; }

• 这里我们允许n为更宽的整数类型（unsigned long long），但求值时会自动转换。
• 若使用uint64_t，__int128需要unsigned __int128。

6.2 递归式的合并

如果需要在递归中间做模，比如：

T modpowRec(T a, U n, T mod) { if (n == 0) return 1 % mod; T half = modpowRec(a, n >> 1, mod); if (n & 1) return (__int128)half * half % mod * a % mod; else return (__int128)half * half % mod; }

注意half先做过模，防止溢出。

7. 负指数与浮点数

7.1 负整数指数

在整数域上，负指数意味着求a的求逆（如果a可逆）。若mod为素数，可以借助费马小定理求逆：

a−n≡(a−1)n(modm)a−n≡(a−1)n(modm)

其中a^{-1} = a^{m-2} \bmod m.

long long modpowNeg(long long a, long long n, long long mod) { // 先取 a 的逆 long long inv_a = modpow(a, mod - 2, mod); // precondition: mod is prime return modpow(inv_a, n, mod); }

7.2 浮点指数

如果题目要求x^n（其中x为浮点数，不取模），可以使用std::pow。但其实快速幂也能配合浮点数使用：

double powFloat(double a, long long n) { double res = 1.0; while (n > 0) { if (n & 1) res *= a; a *= a; n >>= 1; } return res; }

与std::pow相比，它在说明“快速幂”时更显直观。虽然sqrt、log等更高级实现会被优化，但对于一般竞赛来说差别不大。

8. 常见错误与陷阱

1. 忘记取模：若没有 MOD，a * a在大数时会溢出。
2. 使用int而不是long long：尤其在 OJ 的INT_MAX之后测试数据会导致错误。
3. 链式乘法：result = result * a;先乘后取模，但若result过大会溢出。
4. 负数模：在 C++ 中-1 % mod结果为-1，而我们通常需要正模结果。可在取模后加mod再% mod。
5. 复合模（多模）：若需要满足多个模，使用 CRT（Chinese Remainder Theorem）或将每一步都做模。
6. 取n的二进制时使用unsigned long long：避免因为负数右移产生负号。

9. 复杂度分析

• 时间：
  • 递归 & 迭代：Θ(log₂ n)。
  • 若n = 10^18，循环次数约为 60。
  • 乘法__int128速度稍慢，但可接受。
• 空间：
  • 迭代：O(1)。
  • 递归：O(log n)（约 60 层栈）。
• 对mod的限制：如果mod远小于 2⁶³，__int128能保证中间结果不溢。

10. 进阶应用：矩阵快速幂

矩阵幂同样可以使用快速幂思想。设A为n × n矩阵，则：

An=An/2×An/2若 n 为偶(A(n−1)/2×A(n−1)/2)×A若 n 为奇An=An/2×An/2(A(n−1)/2×A(n−1)/2)×A​若 n 为偶若 n 为奇​

实现通常采用自定义Matrix结构，并提供multiply（按模运算）和power（迭代或递归）。

struct Matrix { static const int N = 3; // 例：3x3 long long a[N][N]; Matrix identity() { Matrix I; for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) I.a[i][j] = (i == j); return I; } Matrix operator*(const Matrix& other) const { Matrix res; for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) { __int128 sum = 0; for (int k = 0; k < N; ++k) sum += (__int128)a[i][k] * other.a[k][j]; res.a[i][j] = (long long)(sum % MOD); } return res; } Matrix pow(long long exp) const { Matrix result = identity(); Matrix base = *this; while (exp > 0) { if (exp & 1) result = result * base; base = base * base; exp >>= 1; } return result; } };

10.1 用法示例：斐波那契数

斐波那契数可表示为：

(Fk+1Fk)=(1110)k(F1F0)(Fk+1​Fk​​)=(11​10​)k(F1​F0​​)

所以F_n = (M^n)[0][0]。

long long fib(long long n, long long mod) { Matrix M; M.a[0][0] = 1; M.a[0][1] = 1; M.a[1][0] = 1; M.a[1][1] = 0; return M.pow(n).a[0][0]; }

双倍出-斐波那契（F_{2k}作为F_k * (2*F_{k+1} - F_k)) 亦可利用快速幂来实现。

11. 预先计算与组合

11.1 取模逆元素

在组合数求模时，需要用到阶乘的逆元。根据费马小定理：

x−1≡xm−2(modm)(m 为素数)x−1≡xm−2(modm)(m 为素数)

所以我们可以预先计算fact与invfact：

const int MAXN = 1e6; long long fact[MAXN], invfact[MAXN]; void precompute() { fact[0] = 1; for (int i = 1; i < MAXN; ++i) fact[i] = fact[i-1] * i % MOD; invfact[MAXN-1] = modpow(fact[MAXN-1], MOD-2, MOD); for (int i = MAXN-2; i >= 0; --i) invfact[i] = invfact[i+1] * (i+1) % MOD; } long long C(int n, int k) { if (k < 0 || k > n) return 0; return fact[n] * invfact[k] % MOD * invfact[n-k] % MOD; }

此方法在 O(1) 时间即可求任意C(n, k) (n < 1e6)。

11.2 相关变形

• 求组合数：C(a + b, a)，C(n, k)
• 指数组合：nCr = (n! / r! / (n-r)!) mod M
• 圆盘堆叠：常出现的C(n + k - 1, k)或C(n, k)，同样使用预处理。

12. 负数模、粘模

有时模数M不是素数，或者是int负数。C++ 的取模运算对负数的行为为“保持符号”，导致-1 % 100得到-1，而我们通常想得到99。处理办法：

long long modFix(long long x, long long mod) { return (x % mod + mod) % mod; }

或者在每次取模前做((x % mod) + mod) % mod。

13. 结合多模 & CRT

在有些题目中，需要a^n mod m1、a^n mod m2等多组模运算结果合并为一个大数。此时可使用中国剩余定理（CRT）：

1. 先用快速幂得到各模下的结果r1, r2, …, rk。
2. 通过 CRT 将六个结果合并为一组：

long long CRT(vector<long long> residues, vector<long long> mods) { long long x = 0, M = 1; for (size_t i = 0; i < residues.size(); ++i) { long long m = mods[i]; long long ri = residues[i]; long long t = ((__int128)(ri - x) * modpow(M, m-2, m)) % m; x += M * t; M *= m; } return x; }

M必须在__int128范围内，否则会溢出。

14. 取值范围与边界考虑

选择__int128是最保险的做法；若编译器不支持，可拆分成 64 位乘法，或使用第三方大整数库 (如Boost.Multiprecision::cpp_int)。但大多竞赛的编译器（GCC 9+）都支持__int128。

15. 代码集成与范例

以下给出一个完整、可直接跑通的 CPP 示例，涵盖快速幂、取模、矩阵幂、组合数求模、负指数处理与 CRT，并在main函数里演示多种用法。

#include <bits/stdc++.h> using namespace std; const long long MOD = 1000000007LL; /* ---------- Fast Modular Power ---------- */ long long modpow(long long a, long long n, long long mod = MOD) { long long res = 1 % mod; a %= mod; while (n > 0) { if (n & 1) res = (__int128)res * a % mod; a = (__int128)a * a % mod; n >>= 1; } return res; } /* ---------- Negatives & Positive Mod & CRT helper ---------- */ long long mod_fix(long long x, long long mod) { return (x % mod + mod) % mod; } long long crt(const vector<long long>& rs, const vector<long long>& ms) { long long x = 0, M = 1; for (size_t i = 0; i < rs.size(); ++i) { long long m = ms[i]; long long r = rs[i]; long long t = (__int128)(r - x) * modpow(M, m-2, m) % m; x = (x + M * t) % (M * m); M *= m; } return x; } /* ---------- Matrix 3x3 exemplar ---------- */ struct Matrix { static const int SZ = 3; long long a[SZ][SZ]; Matrix() { memset(a, 0, sizeof(a)); } static Matrix identity() { Matrix I; for (int i = 0; i < SZ; ++i) I.a[i][i] = 1; return I; } Matrix operator*(const Matrix& o) const { Matrix r; long long tmp; for (int i = 0; i < SZ; ++i) for (int j = 0; j < SZ; ++j) { __int128 sum = 0; for (int k = 0; k < SZ; ++k) sum += (__int128)a[i][k] * o.a[k][j]; r.a[i][j] = (long long)(sum % MOD); } return r; } Matrix pow(long long e) const { Matrix r = identity(), b = *this; while (e > 0) { if (e & 1) r = r * b; b = b * b; e >>= 1; } return r; } }; Matrix make_stirling() { // 3x3 example matrix Matrix M; M.a[0][0] = 0; M.a[0][1] = 1; M.a[0][2] = 0; M.a[1][0] = 0; M.a[1][1] = 0; M.a[1][2] = 1; M.a[2][0] = 1; M.a[2][1] = 1; M.a[2][2] = 0; return M; } /* ---------- Precomputation for nCr ---------- */ const int LIM = 2000000; long long fact[LIM+1], invfact[LIM+1]; void precompute_fact() { fact[0] = 1; for (int i = 1; i <= LIM; ++i) fact[i] = fact[i-1] * i % MOD; invfact[LIM] = modpow(fact[LIM], MOD-2); for (int i = LIM; i > 0; --i) invfact[i-1] = invfact[i] * i % MOD; } inline long long C(int n, int k) { if (k < 0 || k > n) return 0; return fact[n] * invfact[k] % MOD * invfact[n-k] % MOD; } /* ---------- Main demo ---------- */ int main() { ios::sync_with_stdio(false); cin.tie(nullptr); /* ① 快速幂常规用法 */ long long a = 1234567890123LL; long long n = 1234567890LL; cout << "a^n mod MOD = " << modpow(a, n) << '\n'; /* ② 负指数的计算（模数必须是素数） */ long long inv_a = modpow(a % MOD, MOD-2); // a^-1 long long pos_n = 100; // a^100 long long neg_n = modpow(inv_a, 100); // a^-100 mod MOD cout << "a^-100 mod MOD = " << neg_n << '\n'; /* ③ 矩阵幂支持：S(-1)^n（示例） */ Matrix M = make_stirling(); Matrix Mn = M.pow(10); cout << "M^10[2][2] = " << Mn.a[2][2] << '\n'; /* ④ 预处理阶乘、逆阶乘，快速组合数 */ precompute_fact(); cout << "C(10,3) = " << C(10,3) << '\n'; // 120 cout << "C(2000000,1000) = " << C(2000000,1000) << '\n'; /* ⑤ 正负模以及 CRT 合并示例 */ long long r1 = modpow(2, 100, 3); // 2^100 mod 3 long long r2 = modpow(2, 100, 5); // 2^100 mod 5 vector<long long> rs = {r1, r2}; vector<long long> ms = {3, 5}; cout << "CRT(2^100 mod 15) = " << crt(rs, ms) << '\n'; return 0; }

上述代码已通过编译器（GCC 12.2 / Clang 14）测试，涵盖了常见场景。若您在 OJ / 代码库中使用，可直接拷贝。

16. 性能微调与实战注意

1. 循环展开：若n较大，可以把while (n)循环拆成十几条if (n & 1) ...，减少分支开销。
2. 关闭 I/O 同步：在大 I/O 场景下，使用ios::sync_with_stdio(false); cin.tie(nullptr);。
3. 编译优化：开启-O3或-march=native，保证编译器把__int128乘法优化为mul+sal/shl。
4. 使用模板：若需要对多种整数（int32,int64,__int128）做快速幂，可写成模板。
5. 避免不必要的% mod：在顶层循环里，如果a已经小于mod，不必再次取模。
6. 实验不同实现：若时间吃紧，可用递归加尾递归保存（inline+register）或将递归改写成for ( ; n; n = n >> 1)的方式。
7. 剖析特殊情况：特别是mod == 1时，无论何种指数，结果都是 0；判断mod == 1可以直接返回 0，避免modpow里取模操作导致 0/0。

17. 结语

快速幂是解决指数问题的底层构件。一次完整、细致的 C++ 实现不只是一个单纯的“算法实现”，更是对算术运算、位运算、循环、递归、模板、整数溢出、取模、矩阵、组合、负数处理、CRT等多方面知识的综合体现。
无论是算法竞赛简单题（如3^1000 % 1e9+7）、中等难度题（矩阵斐波那契）、高阶题（多模合并 + 线性递推）还是科研项目（大数据模运算），掌握快速幂的实现原则与细节都是不可或缺的。

只要能写出一个完整、没有黑洞、可运行、并且自带测试的实现，就意味着你已具备高质量代码的基础与能力。祝你在后续的算法旅程中不断发掘更多应用场景，再次感谢阅读！