快速幂

快速幂

$$计算a^n,在朴素算法下,需要O(n)的时间复杂度$$

$$a^1 * a^1 = a^2 \\ a^2 * a^2 = a^4 \\ a^4 * a^4 = a^8 \\ a^8 * a^8 = a^{16} \\ a^{16} * a^{16} = a^{32} \\ a^{32} * a^{32} = a^{64}$$

$$如上, 根据倍增原理将a^{2^k}转化为了k次计算,时间复杂度为O(logn)$$

$$对于普通形式下的幂运算,如a^{105},则可以写成a^{1+8+32+64},即105的二进制编码1101001$$

long long binEXP(int a, int n)
{
    long long r = 1;
    while (n)
    {
        if (n & 1)
            r = r * a;
       	a *= a;
        n >>= 1;
    }
    return r;
}

应用1: 幂取模

def MODEXPFAST(a, n, m):
    a = a % m
    r = 1
    while n:
        if n & 1:
            r = (r * a) % m
        a = (a ** 2) % m
       	n >>= 1
   	print(r)