Leetcode 50. Pow ( x , n ) 快速幂、取模 C++实现

问题：Leetcode 50. Pow ( x , n )

        实现 pow(x, n) ，即计算 x 的整数 n 次幂函数。

算法：

具体实现流程如下：

代码：

class Solution {
public:double myPow(double x, int N) {double ans = 1;long long n = N;if (n < 0) { // x^-n = (1/x)^nn = -n;x = 1 / x;}while (n) { // 从低到高枚举 n 的每个比特位if (n & 1) { // 这个比特位是 1ans *= x; // 把 x 乘到 ans 中}x *= x; // x 自身平方n >>= 1; // 继续枚举下一个比特位}return ans;}
};

---

取模

         某些题目，由于要计算的答案非常大（超出 64 位整数的范围），会要求把答案对 10⁹ + 7 取模。如果没有处理得当的话，会 WA（错误）或者 TLE（超时）。

        例如计算一堆数字的乘积，如果没有及时取模，乘法会溢出（例如计算结果超出 C++ 中 long long 的最大值），从而得到和预期不符的答案。

        代码实现时，上面的加减乘除通常是这样写的：

MOD = 1_000_000_007// 加
(a + b) % MOD// 减
(a - b + MOD) % MOD// 把任意整数 a 取模到 [0,MOD-1] 中，无论 a 是正是负
(a % MOD + MOD) % MOD// 乘（注意使用 64 位整数）
a * b % MOD// 多个数相乘，要步步取模，防止溢出
a * b % MOD * c % MOD// 除（MOD 是质数且 b 不是 MOD 的倍数）
a * qpow(b, MOD - 2, MOD) % MOD

其中 qpow 为 快速幂。