1.1 思路一：递归#

• 若 N 为偶数，可以先求 x^N/2，然后再平方。
• 若 N 为奇数，可以先求 x^(N-1)/2，然后再平方，再乘以x

快速幂的最基础思想就是上面两条了。

求解 x^N/2，x^(N-1)/2 时也可以用到上面的思路，每次将指数除以2，每次都可以将复杂度降低一半，知道最后指数为1。

1
func quickpow(_ x: Int, _ n: Int) -> Int {
2
    if n == 0 {// 直到最后指数为0
3
        return 1
4
    }
5
    let res = quickpow(x, n/2)
6
    if n%2 != 0 {// n 为奇数
7
        return res * res * x
8
    }
9
    // n为偶数
10
    return res * res
11
}

1.2 思路二：二进制拆分#

我们以 x¹⁴ 为例进行推导。

换个方向，更直观：

推论：

• 设 x 的 N 次幂等于 res
  • 1: 在指数 N 的二进制形式下，从最低位开始左移一位，x自乘一次（和指数N左移一位保持一致）
  • 如果当前位为1
    • 当前位a到最低位，中间位全部置0时表示的值b，x^b的累乘
  • 如果当前位位0
    • 执行1
  • 循环直到指数N等于0

1
func quickpow(_ x: Int, _ n: Int) -> Int {
2
    var res = 1
3
    var x = x
4
    var n = n
5

6
    while n > 0 {
7
        if n & 1 == 1 { // 如果n的当前末位为1
8
            res *= x // res乘上当前的x
9
        }
10
        x *= x// x自乘，当前指数左移一位
11
        n >>= 1// n右移一位，想当于 n / 2
12
    }
13

14
    return res
15
}

1.3 参考#

Pecco-算法学习笔记(4)：快速幂

【朝夕的ACM笔记】杂项-快速幂

2.1 模运算规律#

• (a + b) % p = (a % p + b % p) % p
• (a - b) % p = (a % p - b % p + p) % p
• (a * b) % p = (a % p * b % p) % p
• a^b % p = ((a % p)^b) % p

根据这个规律，可以推导出同余性质

2.2 常见问题场景#

我们经常会看到 输出结果对x取模。这种题目一般考察两点：

• 在原算法的基础上，多一个取模运算来考察你对取模运算规律的掌握
• 大数据时数据增长太快，64 位甚至 128 位的整形无法表示
  • 「剑指Offer」14-II.剪绳子是个典型问题
    • 题解

2.3 利用快速幂，控制数据范围#

14-II.剪绳子 中通过快速幂，结合模运算规律，控制了幂运算结果的范围不会超过 1_000_000_007。

1
func modPow(_ x: Int, _ n: Int) -> Int {
2
    var res = 1
3
    var x = x
4
    var n = n
5

6
    while n > 0 {
7
        if n & 1 == 1 {
8
            res *= x
9
            res %= 1_000_000_007 // 限制了数据范围
10
        }
11
        x *= x
12
        x %= 1_000_000_007 // 限制了数据范围
13
        n >>= 1
14
    }
15

16
    return res
17
}