快速幂

快速幂的作用是在$O(\log_2^n)$的时间复杂度下求出底数的$n$次幂。
快速幂作为ACM基本知识点，是属于必须掌握的一类。

递归理解

根据幂运算规则易得递归式，但递归的写法在时间和空间上可以优化，故并不常见。

$$ a^n = \begin{cases} a^{\frac{n}{2}}*a^{\frac{n}{2}}, \quad x\%2=0\\ a^{\frac{n}{2}}*a^{\frac{n}{2}}*a, \quad x\%2=1 \end{cases} $$

#define LL long long
LL fast_pow(LL a, LL n, LL mod) {
    if(n == 1) return a % mod;
    LL ret = fast_pow(a, n / 2, mod);
    if(n & 1) return a * ret % mod * ret % mod;
    return ret * ret % mod;
}

二进制理解

将$n$进行二进制拆分，有$a^n = \sum_{i = 0}^{\lfloor log_{2}{n}\rfloor} a*2^i*(n\&(1<<i))$。
举个例子：$a^{11}=1*a^8+0*a^4+1*a^2+1*a^1$。

#define LL long long
LL fast_pow(LL a, LL n, LL mod) {
    a %= mod;
    LL ret = 1, tmp = a;
    while(n) {
        if(n & 1) ret = ret * tmp % mod;
        tmp = tmp * tmp % mod;
        n >>= 1;
    }
    return ret;
}

版权属于：小影

本文链接：http://kindkidll.com/index.php/archives/118/

所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。