【常用模板】快速幂
浏览 392 | 评论 0 | 字数 801
TTQ
2020年02月28日
  • 所谓快速幂就是快速算底数的$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 授权协议,转载请注明来源,谢谢!
    评论
    与本文无关评论请发留言板。请不要水评论,谢谢。
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论