※ 引述《Rushia (みけねこ的鼻屎)》之铭言：
: 思路：
: 1.一开始直接递回乘/除结果吃TLE，所以这题很明显要用分治去处理。
一开始吃overflow的：
class Solution
{
public:
double myPow(double x, int n)
{
if (n == 0)
return 1;
if (n > 0)
return x * myPow(x, n - 1);
if (n < 0)
return 1 / (x * myPow(x, -(n + 1)));
return x;
}
};
: 2.指数的特性，3^11 可以被表示为 3 * 3^2 * 3^8，其中因为拆分完的指数字段
: 必定能被二进制表示，上式可被转为：3 * (3^1)^2 * (3^4)^2
: 也就是说我们如果有一个快速的方法可以求出 3 的 2^k 次方，本来需要 n 次乘法
: 才能完成的运算可以被简化为 O(logn) 次。
后面改成处理奇数偶数
class Solution
{
public:
double myPow(double x, int n)
{
if (n == 0)
return 1;
if (n < 0)
return 1 / (x * myPow(x, -(n + 1)));
if (n % 2 != 0)
return x * myPow(x, n - 1);
return myPow(x * x, n / 2);
}
};
变成每次计算一半 n偶数就两个一半相乘
(x * x, n / 2)
n奇数就是这次的次方减一去算偶数结果 再乘一个自己
(x * (x * x, n-1 / 2))