数学-快速幂

快速幂

快速幂，即快速取幂的技巧。

对于在取幂过程中，需要不断取模的过程中（例如费马小定理求模逆元）时，单纯的pow函数已经不再满足我们的需要。我们需要明白pow函数的原理，以方便我们“魔改”pow函数。

定义

快速幂，二进制取幂（Binary Exponentiation),是一个在 的时间计算 的小技巧。

实现

递归形式

按幂的定义而言， 等于 个 相乘，如果我们按照这样的定义实现算法的话，当 足够大时，资源的开销就很大了。

根据指数乘法，, 当 为偶数时, , 对于 为奇数的情况, 无非是在此基础上再乘以 罢了。因此，我们很容易就能得到实现快速幂的递归形式。

1
2
3
4
5
6
7
long long pow(long long a, long long b){
    if(b == 0) return 1;
    long long res = pow(a, b/2);
    if(b % 2 == 1) return res * res * a;
    else
        return res * res;
}

迭代形式

​ 显然，尽管二者理论复杂度差不多，但由于递归会花费一定的开销，因此在实践中迭代形式是更快的。

​ 在二进制中，除以2的操作是等同于右移1位的操作的，同时，同时我们可以将指数转化为二进制，例如 ，我们每次取出其中1的部分，即乘上对应的 的部分，并且每次更新 ，即在每次循环中让a自乘本身，使得 其指数长度增1，显然循环的次数由对应 的二进制数长度所决定，因此显然时间复杂度应该是 级别的。

1
2
3
4
5
6
7
8
9
long long pow(long long a, long long b){
    long long res =1;
    while(b > 0){
        if(b & 1) res = res * a;
        a = a * a;
        b >>=1;
    }
    return res;
}