摘要:
深入快速幂。
朴素快速幂
快速幂,二进制取幂(Binary Exponentiation,也称平方法),是一个在
二进制取幂 的想法是,我们将取幂的任务按照指数的 二进制表示 来分割成更小的任务。
举例:计算
将
我们可以预处理出来
3是怎么来的呢?
因为
那么,对于
而这个预处理的每一个项,都可以由前面的项计算得到。
从二进制最低位到最高位,假设全为1,那么每一项都等于前一项的平方;
假设从低到高位依次为
根据这个思想,写代码的时候,我们动态地让指数右移,让
迭代
1 | long long fastpow(long long a, long long n) |
递归
待更新。