VIRTUALS

the virtual labs for the virtuals

0%

快速幂专题

摘要:
深入快速幂。

朴素快速幂

快速幂,二进制取幂(Binary Exponentiation,也称平方法),是一个在 O(logn) 的时间内计算 an 的小技巧,而暴力的计算需要 O(n) 的时间。

二进制取幂 的想法是,我们将取幂的任务按照指数的 二进制表示 来分割成更小的任务。

举例:计算 313.

313拆成:
313=3(1101)2=383431

我们可以预处理出来31,34,38,一共只需计算3次得到答案。
3是怎么来的呢?
因为323<313<324,所以3=log2(13)

那么,对于an,因为nlog2(n)+1个二进制位,那么当我们预处理出:
a1,a2,a4,a8,,a2log2(n) 后,就只需计算O(logn)次乘法即可计算出an

而这个预处理的每一个项,都可以由前面的项计算得到。
从二进制最低位到最高位,假设全为1,那么每一项都等于前一项的平方;
假设从低到高位依次为101,那么第一项显然为底数本身,第二项为1,第三项并非由第二项得出,而是第一项的平方的平方。

根据这个思想,写代码的时候,我们动态地让指数右移,让a与最低位1相乘,然而每右移一次,相当于指数b除2,等价于a对应地更新成a2。当最低位不为1时,则a继续更新,且不与最低位相乘。

迭代

1
2
3
4
5
6
7
8
9
long long fastpow(long long a, long long n)
{
long long res = 1;
for (; n; n >>= 1) {
if (n & 1) res *= a;
a = a * a;
}
return res;
}

递归

待更新。