快速幂及其模

快速幂

时间复杂度

• O(log2(N))

原理

幂指数以二进制的形式参与计算

然后把a^b转化为 通项为 a^( 2^n(0或1)) 求0到n项和的多项式

代码

ll quick_pow(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a;
        a *= a;
        b /= 2;
    }

    return res;
}

快速幂的模

原理

由模运算a^b%p = ((a%p)^b)%p结合快速幂的原理得出

代码

ll quick_pow_mod(ll a, ll b, ll mod)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b /= 2;
    }

    return res;
}