龟速乘&可靠快速幂

学自【谈谈知识点】快速幂&龟速乘&快速乘 - Cyan_rose的博客 - CSDN博客

基础快速幂

直接上代码

ll speed(ll a,ll b,ll p){
    ll cur=a,ans=1;
    while(b){
        if(b&1) ans=ans*cur%p;
        cur=cur*cur%p;
        b>>=1;
    }
    return ans%p;
}

龟速乘

乘法换成加法，原理差不多就是把其中一个乘数二进制拆分，每次让另一个乘数翻倍，能乘的时候就乘，因为只是翻倍，所以不会超范围。

c++ ll lowspeed(ll a,ll b,ll p){ ll cur=a,ans=0; while(b){ if(b&1) ans=(ans+cur)%p; cur=(cur+cur)%p; b>>=1; } return ans%p; } ll speed(ll a,ll b,ll p){ ll cur=a,ans=1; while(b){ if(b&1) ans=lowspeed(ans,cur,p)%p; cur=lowspeed(cur,cur,p)%p; b>>=1; } return ans%p; }