#import "../template.typ": *
#pagebreak()
= 快速幂

如何计算\(a^n\), \(a \in Z\)? \(a^{100,000,000}\)朴素算法要遍历 100,000,000 次?
复杂度太高.

特殊情况, n 为 2 的幂的时候, 计算$a^64$?

```
a^1 * a^1 = a^2
a^2 * a^2 = a^4
a^4 * a^4 = a^8
a^8 * a^8 = a^16
a^16 * a^16 = a^32
a^32 * a^32 = a^64
```

特殊情况, n 不为 2 的幂的时候, 计算$a^{105}$?

```
105 = 1+8+32+64
105 -> 1 1 0 1 0 0 1
1   -> 0 0 0 0 0 0 1
8   -> 0 0 0 1 0 0 0
32  -> 0 1 0 0 0 0 0
64  -> 1 0 0 0 0 0 0
```

伪代码

```py
function BINEXP(a, n):
    r = 1
    while n != 0
        # if n mod 2==1
        if n & 1 == 1
            r = r*a
        a = a*a
        n = n>>1
    return r
```

#image("images/2023-11-20-11-46-29.png")

时间复杂度 O(logn)

== 应用 1

计算 $a^n \bmod m$

== 应用 2

计算斐波那契数列的第 n 项

== 应用 3

将线性变化重复 n 次.
