上一次手写快速幂还是大一时候的事情了,这次遇到了就顺便复习一下~

快速幂,顾名思义就是快速算幂。

正常计算 x 的 n 次方,办法就是乘 n 次 x 就行,时间复杂度 O(n) 。当然,这个办法慢了。

要快的的话,就把 n 拆成二进制。对与二进制中的第 i 位,如果这一位为 1 ,则代表最后的答案中包含 x 的 2 的 i - 1 次方,也就是说从低位到高位的 1 分别对应了 x, x^2, x^4, x^8, …

这样一来,只需要按位进行累乘,同时这一位需要的乘数可以由上一位转移而来,也就是 x *= x 。时间复杂度 O(logn) 。


Pow(x, n)

Leetcode 50 Pow(x, n)

这题就是快速幂了,不过有几个点需要注意一下:

  • n 为负数的时候需要判断,结果用 1 除以一下答案就行。

  • 传进来的 n 是一个 32 位整数,范围 [−2^31, 2^31 − 1] ,所以直接取绝对值是不行的,需要转换为 64 位整数或者无符号整数。

  • n 为 0 的问题,下面这个写法解决了这个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution
{
public:
double myPow(double x, int n)
{
const auto flag = n >= 0;
auto pow = abs(static_cast<long long>(n));
double ans = 1;

while (pow)
{
if (pow & 1) ans *= x;
x *= x;
pow >>= 1;
}

return flag ? ans : 1 / ans;
}
};

模意义下的快速幂

反正幂的时候取模就好了hhh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
long long qkpow(long long x, long long n, const long long mod)
{
long long ans = 1;
x %= mod;

while (n)
{
if (n & 1) ans = (ans * x) % mod;
x = (x * x) % mod;
n >>= 1;
}

return ans % mod;
}