龟速乘

luckydrawbox · 2021-10-11 15:42:26 · 算法·理论

普通版本

求 a\times b\bmod c，时间复杂度 O(\log b)。

乘法可能爆 \text{long long} 时可以用。

long long Fmul(long long a,long long b,long long c){
    long long ans=0;
    while(b){
        ans=(ans+a*(b&1))%c;
        a=(a+a)%c;
        b>>=1;
    }
    return ans;
}

快速版本

时间复杂度 O(1)。

ll mul(ll a,ll b,ll c){
    ll k=(ll)((1.0L*a*b)/(1.0L*c)),t=a*b-k*c-c;
    while(t<0)t+=c;return t;
}

back