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

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

正常计算 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;
}