C快速幂完整实战讲解1. 背景与意义指数运算a^n是数学与计算机科学中最常见的操作之一。直观的计算方法是把基数a乘n次但是当n很大如数十亿、上亿甚至 10sup18/sup时线性循环的时间复杂度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 是奇数可进一步写成anan/2×an/2若 n 为偶(a(n−1)/2×a(n−1)/2)×a若 n 为奇anan/2×an/2(a(n−1)/2×a(n−1)/2)×a若 n 为偶若 n 为奇这个拆分利用了二进制的特性从高位到低位逐步处理指数二进制位。具体实现有两大变体递归实现直接按上面公式递归求解迭代实现利用指数的最低有效位累积结果同时把指数右移一位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 迭代与递归的比较特点递归迭代空间O(log n)递归栈O(1)性能额外递归函数调用纯循环可读性直观符合公式简洁安全性递归深度偶尔超限无关在极端大数如n 10^9的情况下递归方式完全无问题但如果你在嵌入式或最小化内存场景迭代更稳妥。5. 取模实现模幂当我们需要求a^n mod m特别是m为 10sup9/sup7 等 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 关键技巧使用__int128当a与mod都接近 10sup18/sup 时a * a会溢出 64 位。__int128若编译器支持可以安全处理 128 位整数。按位取模a % mod先对基数做模随后所有乘法保持在[0, mod)范围内避免乘溢出。取模的顺序一定先做乘再做取模而不是先取模后再乘。5.2 典型应用场景需求模幂实现1. 计算a^b mod M如M 1e97)modpow(a, b, M)2. 计算组合C(n, k) mod M用费马小定理C(n, k) fact[n] * invfact[k] * invfact[n-k] mod M其中invfact是modpow(fact, M-2, M)的结果3. 计算斐波那契数F(n) mod M用矩阵快速幂矩阵元素同样做模运算6. 栈与缓存优化可读性与性能6.1 将模幂抽成函数模板在多语言项目中模幂经常被多处调用。使用模板可以让编译器生成类型安全的代码。templatetypename 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. 常见错误与陷阱忘记取模若没有 MODa * a在大数时会溢出。使用int而不是long long尤其在 OJ 的INT_MAX之后测试数据会导致错误。链式乘法result result * a;先乘后取模但若result过大会溢出。负数模在 C 中-1 % mod结果为-1而我们通常需要正模结果。可在取模后加mod再% mod。复合模多模若需要满足多个模使用 CRTChinese Remainder Theorem或将每一步都做模。取n的二进制时使用unsigned long long避免因为负数右移产生负号。9. 复杂度分析时间递归 迭代Θ(log₂ n)。若n 10^18循环次数约为 60。乘法__int128速度稍慢但可接受。空间迭代O(1)。递归O(log n)约 60 层栈。对mod的限制如果mod远小于 2sup63/sup__int128能保证中间结果不溢。10. 进阶应用矩阵快速幂矩阵幂同样可以使用快速幂思想。设A为n × n矩阵则AnAn/2×An/2若 n 为偶(A(n−1)/2×A(n−1)/2)×A若 n 为奇AnAn/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 用法示例斐波那契数斐波那契数可表示为(Fk1Fk)(1110)k(F1F0)(Fk1Fk)(1110)k(F1F0)所以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_{k1} - F_k)) 亦可利用快速幂来实现。11. 预先计算与组合11.1 取模逆元素在组合数求模时需要用到阶乘的逆元。根据费马小定理x−1≡xm−2(modm)(m 为素数)x−1≡xm−2(modm)(m 为素数)所以我们可以预先计算fact与invfactconst 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[i1] * (i1) % 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先用快速幂得到各模下的结果r1, r2, …, rk。通过 CRT 将六个结果合并为一组long long CRT(vectorlong long residues, vectorlong 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. 取值范围与边界考虑场景取值范围推荐实现int 2sup31/sup 2sup31/sup迭代使用long long进行乘法long long 2sup63/sup 2sup63/sup__int128乘法需要正模 2sup63/sup__int128mod取模取模素数1e971e97long long足够long long*long long生产64 位__int128仍是安全最佳非素数 mod任何同自行限制中间乘可以到mod^2需__int128选择__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 vectorlong long rs, const vectorlong 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[LIM1], invfact[LIM1]; 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 vectorlong long rs {r1, r2}; vectorlong long ms {3, 5}; cout CRT(2^100 mod 15) crt(rs, ms) \n; return 0; }上述代码已通过编译器GCC 12.2 / Clang 14测试涵盖了常见场景。若您在 OJ / 代码库中使用可直接拷贝。16. 性能微调与实战注意循环展开若n较大可以把while (n)循环拆成十几条if (n 1) ...减少分支开销。关闭 I/O 同步在大 I/O 场景下使用ios::sync_with_stdio(false); cin.tie(nullptr);。编译优化开启-O3或-marchnative保证编译器把__int128乘法优化为mulsal/shl。使用模板若需要对多种整数int32,int64,__int128做快速幂可写成模板。避免不必要的% mod在顶层循环里如果a已经小于mod不必再次取模。实验不同实现若时间吃紧可用递归加尾递归保存inlineregister或将递归改写成for ( ; n; n n 1)的方式。剖析特殊情况特别是mod 1时无论何种指数结果都是 0判断mod 1可以直接返回 0避免modpow里取模操作导致 0/0。17. 结语快速幂是解决指数问题的底层构件。一次完整、细致的 C 实现不只是一个单纯的“算法实现”更是对算术运算、位运算、循环、递归、模板、整数溢出、取模、矩阵、组合、负数处理、CRT等多方面知识的综合体现。无论是算法竞赛简单题如3^1000 % 1e97、中等难度题矩阵斐波那契、高阶题多模合并 线性递推还是科研项目大数据模运算掌握快速幂的实现原则与细节都是不可或缺的。只要能写出一个完整、没有黑洞、可运行、并且自带测试的实现就意味着你已具备高质量代码的基础与能力。祝你在后续的算法旅程中不断发掘更多应用场景再次感谢阅读 C++快速幂完整实战讲解
C快速幂完整实战讲解1. 背景与意义指数运算a^n是数学与计算机科学中最常见的操作之一。直观的计算方法是把基数a乘n次但是当n很大如数十亿、上亿甚至 10sup18/sup时线性循环的时间复杂度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 是奇数可进一步写成anan/2×an/2若 n 为偶(a(n−1)/2×a(n−1)/2)×a若 n 为奇anan/2×an/2(a(n−1)/2×a(n−1)/2)×a若 n 为偶若 n 为奇这个拆分利用了二进制的特性从高位到低位逐步处理指数二进制位。具体实现有两大变体递归实现直接按上面公式递归求解迭代实现利用指数的最低有效位累积结果同时把指数右移一位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 迭代与递归的比较特点递归迭代空间O(log n)递归栈O(1)性能额外递归函数调用纯循环可读性直观符合公式简洁安全性递归深度偶尔超限无关在极端大数如n 10^9的情况下递归方式完全无问题但如果你在嵌入式或最小化内存场景迭代更稳妥。5. 取模实现模幂当我们需要求a^n mod m特别是m为 10sup9/sup7 等 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 关键技巧使用__int128当a与mod都接近 10sup18/sup 时a * a会溢出 64 位。__int128若编译器支持可以安全处理 128 位整数。按位取模a % mod先对基数做模随后所有乘法保持在[0, mod)范围内避免乘溢出。取模的顺序一定先做乘再做取模而不是先取模后再乘。5.2 典型应用场景需求模幂实现1. 计算a^b mod M如M 1e97)modpow(a, b, M)2. 计算组合C(n, k) mod M用费马小定理C(n, k) fact[n] * invfact[k] * invfact[n-k] mod M其中invfact是modpow(fact, M-2, M)的结果3. 计算斐波那契数F(n) mod M用矩阵快速幂矩阵元素同样做模运算6. 栈与缓存优化可读性与性能6.1 将模幂抽成函数模板在多语言项目中模幂经常被多处调用。使用模板可以让编译器生成类型安全的代码。templatetypename 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. 常见错误与陷阱忘记取模若没有 MODa * a在大数时会溢出。使用int而不是long long尤其在 OJ 的INT_MAX之后测试数据会导致错误。链式乘法result result * a;先乘后取模但若result过大会溢出。负数模在 C 中-1 % mod结果为-1而我们通常需要正模结果。可在取模后加mod再% mod。复合模多模若需要满足多个模使用 CRTChinese Remainder Theorem或将每一步都做模。取n的二进制时使用unsigned long long避免因为负数右移产生负号。9. 复杂度分析时间递归 迭代Θ(log₂ n)。若n 10^18循环次数约为 60。乘法__int128速度稍慢但可接受。空间迭代O(1)。递归O(log n)约 60 层栈。对mod的限制如果mod远小于 2sup63/sup__int128能保证中间结果不溢。10. 进阶应用矩阵快速幂矩阵幂同样可以使用快速幂思想。设A为n × n矩阵则AnAn/2×An/2若 n 为偶(A(n−1)/2×A(n−1)/2)×A若 n 为奇AnAn/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 用法示例斐波那契数斐波那契数可表示为(Fk1Fk)(1110)k(F1F0)(Fk1Fk)(1110)k(F1F0)所以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_{k1} - F_k)) 亦可利用快速幂来实现。11. 预先计算与组合11.1 取模逆元素在组合数求模时需要用到阶乘的逆元。根据费马小定理x−1≡xm−2(modm)(m 为素数)x−1≡xm−2(modm)(m 为素数)所以我们可以预先计算fact与invfactconst 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[i1] * (i1) % 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先用快速幂得到各模下的结果r1, r2, …, rk。通过 CRT 将六个结果合并为一组long long CRT(vectorlong long residues, vectorlong 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. 取值范围与边界考虑场景取值范围推荐实现int 2sup31/sup 2sup31/sup迭代使用long long进行乘法long long 2sup63/sup 2sup63/sup__int128乘法需要正模 2sup63/sup__int128mod取模取模素数1e971e97long long足够long long*long long生产64 位__int128仍是安全最佳非素数 mod任何同自行限制中间乘可以到mod^2需__int128选择__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 vectorlong long rs, const vectorlong 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[LIM1], invfact[LIM1]; 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 vectorlong long rs {r1, r2}; vectorlong long ms {3, 5}; cout CRT(2^100 mod 15) crt(rs, ms) \n; return 0; }上述代码已通过编译器GCC 12.2 / Clang 14测试涵盖了常见场景。若您在 OJ / 代码库中使用可直接拷贝。16. 性能微调与实战注意循环展开若n较大可以把while (n)循环拆成十几条if (n 1) ...减少分支开销。关闭 I/O 同步在大 I/O 场景下使用ios::sync_with_stdio(false); cin.tie(nullptr);。编译优化开启-O3或-marchnative保证编译器把__int128乘法优化为mulsal/shl。使用模板若需要对多种整数int32,int64,__int128做快速幂可写成模板。避免不必要的% mod在顶层循环里如果a已经小于mod不必再次取模。实验不同实现若时间吃紧可用递归加尾递归保存inlineregister或将递归改写成for ( ; n; n n 1)的方式。剖析特殊情况特别是mod 1时无论何种指数结果都是 0判断mod 1可以直接返回 0避免modpow里取模操作导致 0/0。17. 结语快速幂是解决指数问题的底层构件。一次完整、细致的 C 实现不只是一个单纯的“算法实现”更是对算术运算、位运算、循环、递归、模板、整数溢出、取模、矩阵、组合、负数处理、CRT等多方面知识的综合体现。无论是算法竞赛简单题如3^1000 % 1e97、中等难度题矩阵斐波那契、高阶题多模合并 线性递推还是科研项目大数据模运算掌握快速幂的实现原则与细节都是不可或缺的。只要能写出一个完整、没有黑洞、可运行、并且自带测试的实现就意味着你已具备高质量代码的基础与能力。祝你在后续的算法旅程中不断发掘更多应用场景再次感谢阅读