快速幂算法详解

一、核心数学原理

1. 模运算性质
   [ (a \times b) \mod p = \left[(a \mod p) \times (b \mod p)\right] \mod p ]
   作用：在计算中逐步取模，防止数值溢出。

2. 幂运算分解
   利用指数的二进制分解，将计算 (a^b) 转化为多个子问题：
   [ a^b = \begin{cases} (a^{b/2})^2 & \text{若 } b \text{ 为偶数} \ a \times (a^{(b-1)/2})^2 & \text{若 } b \text{ 为奇数} \end{cases} ]

二、算法步骤

1. 初始化

   • 结果变量 ans = 1（单位元）
   • 底数 a 先取模：a %= c

2. 循环处理指数

   • 奇偶判断：若指数 b 的最低位为 1（即 b & 1 为真），将当前底数累积到结果
   • 底数平方：每次循环将底数平方并取模
   • 指数折半：右移指数 b >>= 1（等价于 b /= 2）

3. 终止条件

   • 当指数 b 降为 0 时结束循环

三、代码实现

typedef long long ll;

ll quick_pow(ll base, ll exponent, ll mod) {
    ll result = 1;              // 初始化为乘法单位元 1
    base %= mod;                // 预处理底数取模
    while (exponent > 0) {      // 指数未耗尽时循环
        if (exponent & 1) {     // 当前二进制位为 1（奇数）
            result = (result * base) % mod;
        }
        base = (base * base) % mod; // 底数平方
        exponent >>= 1;         // 指数右移一位（整除 2）
    }
    return result;
}

四、关键特性

五、示例演算

以 (3^{10} \mod 1000) 为例：

1. (3^{10} = (3^5)^2)
2. (3^5 = 3 \times (3^2)^2 = 3 \times 9^2 = 3 \times 81 = 243)
3. (243^2 = 59049 \rightarrow 59049 \mod 1000 = 49)
4. 最终结果：(49)

六、常见错误

七、扩展应用

1. 矩阵快速幂：求解斐波那契数列 (O(\log n)) 解法
2. 模逆元计算：结合费马小定理求 (a^{-1} \mod p)（当 (p) 为质数时）
3. 多重取模：处理形如 (a^{b^c} \mod p) 的嵌套幂

整理后的内容保持与之前知识体系一致的 Markdown 表格和公式风格，强化了算法核心思想的表达，并补充了实际应用场景的说明。