Algorithm-快速幂算法和快速幂取模算法

Posted on In Word count in article: 2.2k Reading time ≈ 2 mins.

好久没做算法题，上周打周赛时，发现自己忘了怎么做快速幂取模，第二道题 (2550 猴子碰撞的方法数)被卡了时间。所以准备最近把常用的一些优化算法效率的技巧总结一下，顺便测试下博客的代码插件是否正常。

前置知识

费马小定理 (Fermat's little theorem)

Fermat's little theorem[1] states that if p is a prime number, then for any integer a, the number $a^{p} -a$ is an integer multiple of p. In the notation of modular arithmetic, this is expressed as
$$a^{p} \equiv a\ (mod\ p)$$
If a is not divisible by p, that is if a is coprime to p, Fermat's little theorem is equivalent to the statement that $a^{p − 1} − 1$ is an integer multiple of p, or in symbols:
$$a^{p-1} \equiv 1\ (mod\ p)$$

快速幂 (Binary Exponentiation)

原理

快速幂，也叫二进制取幂，是一个在 $\Theta(\log n)$ 的时间内计算 $a^n$ 的小技巧，而暴力的计算需要 $\Theta(n)$ 的时间。

二进制取幂的想法是把$a^n$的指数 n 表示成二进制形式，然后按照二进制表示把取幂划分成子任务去求解，这样可以通过递归简单实现。

首先我们将 $n$ 表示为 2 进制，举一个例子：

$$
3^{13} = 3^{(1101)_2} = 3^8 \cdot 3^4 \cdot 3^1
$$

$$
\begin{align*}
3^1 &= 3 \\
3^2 &= \left(3^1\right)^2 = 3^2 = 9 \\
3^4 &= \left(3^2\right)^2 = 9^2 = 81 \\
3^8 &= \left(3^4\right)^2 = 81^2 = 6561
\end{align*}
$$

因此为了计算 $3^{13}$，我们只需要将对应二进制位为 1 的整系数幂乘起来就行了：

$$
3^{13} = 6561 \cdot 81 \cdot 3 = 1594323
$$

将上述过程说得形式化一些，如果把 $n$ 写作二进制为 $(n_tn_{t-1}\cdots n_1n_0)_2$，那么有：

$$
n = n_t2^t + n_{t-1}2^{t-1} + n_{t-2}2^{t-2} + \cdots + n_12^1 + n_02^0
$$

其中 $n_i\in{0,1}$。那么就有

$$
\begin{aligned}
a^n & = (a^{n_t 2^t + \cdots + n_0 2^0})\\
& = a^{n_0 2^0} \times a^{n_1 2^1}\times \cdots \times a^{n_t2^t}
\end{aligned}
$$

算法实现

递归版

1
2
3
4
5
6
7
8
def binpow(a, b):
    if b == 0:
        return 1
    res = binpow(a, b // 2)
    if (b % 2) == 1:
        return res * res * a
    else:
        return res * res

非递归版

1
2
3
4
5
6
7
8
def binpow(a, b):
    res = 1
    while b > 0:
        if (b & 1):
            res = res * a
        a = a * a
        b >>= 1
    return res

显而易见，非递归算法会有比递归算法更高的效率，即使他们的理论复杂度都一样。

快速幂取模

对于基本的加、减、乘、乘方运算，模运算并不会产生影响，因为满足：

$$
\begin{align*}
(a + b) \pmod p = (a \pmod p + b \pmod p) \pmod p \\
(a - b) \pmod p = (a \pmod p - b \pmod p) \pmod p \\
(a * b) \pmod p = (a \pmod p * b \pmod p) \pmod p \\
(a^b) \pmod p = ((a \pmod p)^b) \pmod p
\end{align*}
$$

因此，快速幂取模运算可以参考上面算法，分奇偶指数两种情况来实现：

1
2
3
4
5
6
7
8
9
def binpow(a, b, m): # a^b % m
    res = 1
    a = a % m
    while b > 0:
        if (b & 1):
            res = res * a % m
        a = a * a % m
        b >>= 1
    return res

TODO

这次测试发现 hexo 自带的 markdown 渲染有问题，会把英文半角符号渲染为全角。另外 next 使用的 mathjax 使用过程中也有点瑕疵，无法用标准 LaTeX 语言渲染出来，比如无法支持用\在公式块内换行。目前发现原因是 hexo 会首先将 markdown 转换为 html，然后 mathjax 再根据 html 渲染 LaTeX 公式，因此\就变成了\，接下来会想办法解决这些问题。

下周计划总结一些常用的数论算法，便于更高效解决 leetcode 题目。

  1. 1.Wikipedia: Fermat's little theorem ↩