1.参考
2.思路
如果直接求取 M^n，时间复杂度是 O(n)，可以用快速幂算法来加速这里 M^n的求取, 简化时间复杂度为 O(logn)
主体思路就是不求 M^n 而是求 M^(n/2), 然后先不求M^(n/2), 先求M^(n/4)
代码
1.递归实现快速幂
最直接的写法是使用递归:(求x^n)
这里if (n & 1) 是判断奇偶性的, 决定是 midmidx 还是 mid*mid, 结束条件 x^0 = 1;
double _myPow(double x, long long n)
{
if (n == 0)
return 1;
if (n < 0)
return 1 / _myPow(x, -n);
double mid = _myPow(x, n / 2);
if (n & 1)
return mid * mid * x;
return mid * mid;
}
2.二进制分解
此外还有另外一个代码实现技巧：二进制分解，n -> 1, 2, 4, 8, 16, 32。n 可以分解为 2 的幂次的和 。
例如 13 = 8 + 4 + 1, 求 a^13 需要求 a^8, a^4, a^1, 可以用变量存 a^1, a^2, ..., a^(n-1)
如果当前幂次是 n 需要的，则加到结果中。如何判断当前幂次是否需要，可以用位掩码来决定，即下面代码中的 n&1。
在代码中，通过循环进行迭代，每次迭代都将指数 N 右移一位（相当于除以 2），同时将底数 M 平方。
这样就相当于把指数 N 不断地除以 2，并且将底数 M 不断地平方，直到指数 N 变为 0。
在每一次迭代中，如果当前位为 1（即 n & 1 的结果为非零），就将结果乘以当前的底数 M。
主要思路就是标志+还原(标志:这里通过二进制位是否为1判断是否相乘; 还原: 配合a *= a; 底数a平方次增长, 还原对应的二进制位数使用 n >>= 1即可解决)
比如像13 = 1101
我们这里的 a^1 对应的第0位开始判断, 如果为1, 说明需要乘上;
然后
int quickpower(int a, int n)
{
// a==0 && n==0 特判
int ans = 1; // n = 0 时候不进循环
while(n)
{
if(n & 1) ans *= a;
a *= a;
n >>= 1;
}
return ans;
}