> For the complete documentation index, see [llms.txt](https://ryukiedev.gitbook.io/wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/ji-qiao/03.-kuai-su-mi.md).

# 03.快速幂

## 前言

幂运算是我们最常用的运算之一。如果我们要求 x 的 N 次幂，那么想当然的就会写出一个 N 次的循环，然后累乘得到结果。这种幂运算的复杂度是O(N)。

```swift
var res = 1
for _ in 0..<n {
    res *= x
}
return res
```

## 一、 快速幂

***那么有没有更快的运算方式呢？***

在计算机领域有一种常用的快速幂算法：`蒙哥马利幂（Montgomery reduction）算法`。将复杂度&#x4ECE;***O(N)*** 降到了 ***O(logN)***

### 1.1 思路一：递归

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

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

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

#### Swift实现

* 这里不考虑大数，仅作为思路展示

```swift
func quickpow(_ x: Int, _ n: Int) -> Int {
    if n == 0 {// 直到最后指数为0
        return 1
    }
    let res = quickpow(x, n/2)
    if n%2 != 0 {// n 为奇数
        return res * res * x
    }
    // n为偶数
    return res * res
}
```

### 1.2 思路二：二进制拆分

我们以 x14 为例进行推导。

&#x20;x14(10) = x1110(2) = x1000(2) \* x100(2) \* x10(2)

换个方向，更直观：

&#x20;x1110(2) = x10(2) \* x100(2) \* x1000(2)

推论：

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

|   当前位  |  指数b |            res            |
| :----: | :--: | :-----------------------: |
| 111`0` |   0  |           x0(2)           |
| 11`1`0 |  10  |           x10(2)          |
| 1`1`10 |  100 |     x10(2) \* x100(2)     |
| `1`110 | 1000 | x10(2) *x100(2)* x1000(2) |

#### Swift实现

* 这里不考虑大数，仅作为思路展示

```swift
func quickpow(_ x: Int, _ n: Int) -> Int {
    var res = 1
    var x = x
    var n = n

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

    return res
}
```

### 1.3 参考

[Pecco-算法学习笔记(4)：快速幂](https://zhuanlan.zhihu.com/p/95902286)

[【朝夕的ACM笔记】杂项-快速幂](https://zhuanlan.zhihu.com/p/112312044)

## 二、 快速幂取模

### 2.1 模运算规律

* (a + b) % p = (a % p + b % p) % p&#x20;
* (a - b) % p = (a % p - b % p + p) % p&#x20;
* (a *b) % p = (a % p* b % p) % p&#x20;
* ab % p = ((a % p)b) % p&#x20;

> 根据这个规律，可以推导出[同余性质](/wiki/shu-ju-jie-gou-yu-suan-fa/ji-qiao/02.-tong-yu-xing-zhi.md)

### 2.2 常见问题场景

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

* 在原算法的基础上，多一个取模运算来考察你对取模运算规律的掌握
* 大数据时数据增长太快，64 位甚至 128 位的整形无法表示
  * [「剑指Offer」14-II.剪绳子](/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/14ii.-jian-sheng-zi.md)是个典型问题
    * [题解](https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/tan-xin-kuai-su-mi-by-happy-austin9mq-6bxz/)

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

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

```swift
func modPow(_ x: Int, _ n: Int) -> Int {
    var res = 1
    var x = x
    var n = n

    while n > 0 {
        if n & 1 == 1 {
            res *= x
            res %= 1_000_000_007 // 限制了数据范围
        }
        x *= x
        x %= 1_000_000_007 // 限制了数据范围
        n >>= 1
    }

    return res
}
```