首页 > itarticle > yusijia’s blog qmul

yusijia’s blog qmul

admin 11月 12, 2020 0

Contents

快速乘

快速幂顾名思义，就是快速算某个数的多少次幂。其时间复杂度为 O(logN)，与朴素的O(N)相比效率有了极大的提高。可以将其扩展出快速乘


long long (long long a, long long b, long long mod)
{
    long long ans = 0;
    while(b){
        if(b & 1)
            ans = (ans + a) % mod;
        a = (a << 1) % mod;
        b >>= 1;
    }
    return ans;
}