所谓快速幂就是快速算底数的$n$次幂。其时间复杂度为 $O(\log_2 X)$， 与朴素的$O(N)$相比效率有了极大的提高。

思路

快速幂可以使用位运算来实现。
比如，我们需要求得$a$的$b$次方。

1. 把$b$转化为二进制数，该二进制数第$i$位的权为$2^{i-1}$
2. 依次相乘

例如

$a^{11}=a^{2^{0}+2^{1}+2^{3}}$

$11$的二进制是$1011$

$11=2^{3}\times 1+2^{2}\times 0+2^{1}\times 1+2^{0}\times 1$

因此，我们将$a^{11}$转化为算$a^{2^{0}}\times a^{2^{1}}\times a^{2^{3}}$

实现

b & 1   //取b二进制的最低位，判断和1是否相同，相同返回1，否则返回0，可用于判断奇偶
b >> 1  //把b的二进制右移一位，即去掉其二进制位的最低位

代码

ll qpow(ll a,ll b,ll m)
{
    ll ans=1;
    ll base = a;
    while(b>0)
    {
        if(b&1)
            ans = (ans * base) % m;
        base = (base * base) % m;
        b >>= 1;
    }
    return ans;
}

接口

$a$为底数，$b$为指数，$m$为需要取的模。

本文作者：TTQ
本文链接：https://blog.ponder.fun/archives/29.html
最后修改时间：2021-02-16 10:21:55
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！