快速幂算法

📌 核心概念

快速幂（Fast Power）通过二进制拆分，将幂运算从O(n)优化到O(log n)。

原理：

a^n = a^(2^k1 + 2^k2 + ... + 2^km)
    = a^(2^k1) * a^(2^k2) * ... * a^(2^km)

💻 算法实现

🎯 经典应用

💡 算法技巧

1. 二进制拆分

例如：3^13
13的二进制：1101

3^13 = 3^(8+4+1)
     = 3^8 * 3^4 * 3^1
     = 6561 * 81 * 3
     = 1594323

📊 复杂度对比

方法	时间复杂度	空间复杂度	适用场景
暴力乘法	O(n)	O(1)	n很小
快速幂	O(log n)	O(1)	n很大
矩阵快速幂	O(k³ log n)	O(k²)	递推问题，k为矩阵维度

Go 代码

// 整数快速幂
func quickPow(a, n int) int {
    result := 1
 
    for n > 0 {
        if n&1 == 1 {
            result *= a
        }
        a *= a
        n >>= 1
    }
 
    return result
}
 
// 快速幂取模
func quickPowMod(a, n, mod int) int {
    result := 1
    a %= mod
 
    for n > 0 {
        if n&1 == 1 {
            result = (result * a) % mod
        }
        a = (a * a) % mod
        n >>= 1
    }
 
    return result
}
 
// Pow(x, n)
func myPow(x float64, n int) float64 {
    if n < 0 {
        x = 1 / x
        n = -n
    }
 
    result := 1.0
 
    for n > 0 {
        if n&1 == 1 {
            result *= x
        }
        x *= x
        n >>= 1
    }
 
    return result
}

🎯 经典题目

题目	LeetCode	关键点
Pow(x, n)	50	快速幂
超级次方	372	递归+快速幂
第N个神奇数字	878	二分+容斥
矩形区域不超过K的最大数值和	363	前缀和+二分

---

返回：数学算法