计算 $a$ 的 $n$ 次方表示将 $n$ 个 $a$ 乘在一起:$a^{n} = \underbrace{a \times a \cdots \times a}_{n\text{ 个 a}}$。然而当 $a,n$ 太大的时侯,这种方法就不太适用了。不过我们知道:$a^{b+c} = a^b \cdot a^c,,,a^{2b} = a^b \cdot a^b = (a^b)^2$。二进制取幂的想法是,我们将取幂的任务按照指数的 二进制表示 来分割成更小的任务。
首先我们将 $n$ 表示为 2 进制,举一个例子:
$$ 3^{13} = 3^{(1101)_2} = 3^8 \cdot 3^4 \cdot 3^1 $$
一个二进制全是1的数N可以表示为 ${2^k} - 1$ (想象左移操作符) 那么 $n$ 最多有 $\lfloor \log_2 n \rfloor + 1$ 个二进制位,因此当我们知道了 $a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log_2 n \rfloor}}$ 后,通过对a
不断倍增 只有在二进制数为1的情况下才选择相乘 具体看下面举例
我们只用计算 $\Theta(\log n)$ 次乘法就可以计算出 $a^n$。
于是我们只需要知道一个快速的方法来计算上述 3 的 $2^k$ 次幂的序列。这个问题很简单,因为序列中(除第一个)任意一个元素就是其前一个元素的平方。举一个例子:
$$ \begin{align} 3^1 &= 3 \newline 3^2 &= \left(3^1\right)^2 = 3^2 = 9 \newline 3^4 &= \left(3^2\right)^2 = 9^2 = 81 \newline 3^8 &= \left(3^4\right)^2 = 81^2 = 6561 \newline \end{align} $$
因此为了计算 $3^{13}$,我们只需要将对应二进制位为 1 的整系数幂乘起来就行了:
因为第三位(从右往左)二进制数为0所以没有选择 $$ 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} $$
根据上式我们发现,原问题被我们转化成了形式相同的子问题的乘积,并且我们可以在常数时间内从 $2^i$ 项推出 $2^{i+1}$ 项。
这个算法的复杂度是 $\Theta(\log n)$ 的,我们计算了 $\Theta(\log n)$ 个 $2^k$ 次幂的数,然后花费 $\Theta(\log n)$ 的时间选择二进制为 1 对应的幂来相乘。
|
|
练习: P1226 【模板】快速幂 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
(a*b) % c = (a%c * b % c) % c
|
|
参考:
oiwiki