【专题】快速幂

vectorSpace-blog / 2023-08-10 / 原文

快速幂

模板题：P1226 【模板】快速幂 | 取余运算

快速幂是同余的一个延伸：
给定三个整数 a, b, p，求 a^b mod p 的值。

前引

如果直接暴力求解 pow(a, b) % p 显然是不可取的：先不论时间的花费，其中 pow(a, b) 得到的结果就很有可能超出了数据范围。那如果利用 ，即每步取余后再相乘，这样可以规避数据溢出。但时间复杂度为 O(n) ，n 为次数 b ，b < 2³¹，很明显会 TLE 。

//暴力解法1（**溢出**）：
//include <cmath>
int power(int a, int b, int p) {
    return pow(a, b) /*问题所在*/ % p;
}
//暴力解法2（**超时**）：
int power(int a, int b, int p) {
    int ans = 1;
    for (; b--; /*问题所在*/ )
    ans = a % p * ans, ans %= p;
    return ans;
}

这两种错误的代码逻辑清晰，可暴力求解对于较大的数据则无用武之地。

正文

分治思想：可以将 B 进行二进制分解，分解成一个个子任务再计算:

a^b = 1 !b

　　 a • a^{b - 1} b & 1

　　 a^{b >> 1} • a^{b >> 1} !(b & 1)

快速幂的思想大抵如此：利用分治算法分解，之后在计算的过程中再进行取模运算时，效率便能让人满意许多。

//递归写法参考：
int qpow(int a, int b, int p) {
    if (!b) return 1;
    a %= p;
    int res = qpow(a, b >> 1, p);
    if (b & 1) return (long long)res * res * a % p;
    return res * res % p;
}

不过因为递归本身有开销，所以一般把递归式的写法改成非递归式的，以实现这种思路、算法本应有的优秀效率。（优化）

//非递归式写法（快速幂）：
int qpow(int a, int b, int p) {
    int ans = 1;
    for (; b; b >>= 1, a = (long long)a * a % p)
    if (b & 1)
    ans = (long long)ans * a % p;
    return ans;
}