快速幂与模运算
快速幂（Fast Exponentiation，又称二进制幂）是一种在 O(log n) 时间内计算 a^n 的算法——把朴素 O(n) 的「连乘 n 次」优化到「逐位累乘」，核心是把指数 n 按二进制分解，遇到二进制位为 1 就累乘当前底数，每轮底数自平方、指数右移一位。它与模运算天然搭档：在密码学（RSA）、数论（费马小定理求逆元）、组合数学（大组合数取模 C(n,k) mod p）这类场景里，结果动辄天文数字，必须边算边取模防止中间值溢出——而模运算的加、减、乘可分配性 (a⊙b) mod p = ((a mod p) ⊙ (b mod p)) mod p 保证了「每步取模」不改变最终结果。两者合起来，是竞赛与面试里「数论模板题」的基石。
快速幂的全部考点都源于一个数学事实：指数的二进制分解 ⇒ O(log n) 次乘法。由此衍生出三大主题：①快速幂本身（递归写法 f(n)=f(n/2)²×(n 奇? a : 1) 与迭代写法「底数自平方、指数右移、位 1 累乘」）；②取模版快速幂（每步 %p 防溢出，配合模运算六性质保证正确）；③快速幂的应用（费马小定理 a^(p-1)≡1 mod p 求乘法逆元 a^(p-2) mod p、矩阵快速幂把斐波那契的递推从 O(n) 降到 O(log n)）。其中费马小定理求逆元是组合数取模 C(n,k) = n!/(k!(n-k)!) mod p 的关键一环（除法在模意义下不存在，要用逆元转乘法），矩阵快速幂则把快速幂从「数的自乘」推广到「矩阵的自乘」——思想完全一致，只是乘法变成了矩阵乘法。
评价
优点
- O(log n) 时间：指数二进制分解，乘法次数从 n 次降到约 log₂n 次——算
2^1000只需约 10 次乘法，朴素法要 1000 次 - 常数小、实现短：迭代版核心就一个
while循环 + 几行位运算，是性价比最高的优化之一 - 天然支持取模：每步
%p把中间值压在[0,p)内，彻底避免大数溢出 - 可推广性强：从「数的幂」推广到「矩阵幂」「多项式幂」——只要满足结合律，就能套快速幂模板
缺点
- 只对「重复自乘」有效：若运算是普通加法而非自乘（如
a*n），快速幂退化为快速乘（俄罗斯农民乘法），思想同源但场景不同 - 取模后除法失效：模运算对加、减、乘可分配，但 (a/b) mod p ≠ (a mod p)/(b mod p)——除法必须借助乘法逆元（费马小定理
a^(p-2) mod p，要求 p 为质数） - 大指数需防递归栈溢出：递归版对超大指数（如
n=10^18）可能栈过深，工程上偏好迭代版 - 矩阵快速幂构造转移矩阵有门槛：要把递推关系写成
状态矩阵 × 转移矩阵的形式，初学者容易在矩阵构造上卡住
本叶地图
- 入门 —— 为何需要快速幂（朴素 O(n) 太慢）、二进制分解思想、模运算六性质、边算边取模防溢出
- 快速幂原理：二进制分解 —— 递归 + 迭代两种写法、O(log n) 分析、取模版快速幂（每步 %p）、代码模板
- 模运算性质与应用 —— 模运算六性质、大数取模（BigInt）、费马小定理求逆元、矩阵快速幂引入（斐波那契 O(log n)）
- 参考 —— 快速幂代码模板（递归/迭代/取模）、模运算性质表、费马小定理逆元、易错点清单、权威链接
交互演示
- 快速幂可视化演示 —— 二进制分解逐位累乘的过程