【专题】快速幂

2023-08-10 14:53:00 来源：博客园

快速幂

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

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

(资料图)

前引

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

//暴力解法1（**溢出**）：//include 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;}

类似于二分：由于每次计算都会把次数（即 b ）减少一半，问题的规模也跟着降低到原来的一般。快速幂的时间复杂度是优秀的 O(log n)。（底数为2）

快速幂在数论题中还有一些拓展，但都不在相同的讨论范围之内，故此处不作过多介绍。

关键词：