1. x的平方根

二分查找

class Solution {
public:
    int mySqrt(int x) {
        int left = 1, right = x;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(mid > x / mid)
            {
                right = mid - 1;
            }
            else if(mid < x / mid)
            {
                left = mid + 1;
            }
            else if(mid == x / mid)
            {
                return mid;
            }
        }
        return right;
    }
};

2. 快速幂

• 二分法

每次把n缩小一半

class Solution {
public:
    double myPow(double x, int n) {
        if(n == 0) return 1;
        if(n == 1) return x;
        if(n == -1) return 1.0 / x;
        double v = myPow(x, n / 2);
        v *= v;
        if(n < 0 && n % 2){
            v = 1.0 / x * v;
        }
        if(n > 0 && n % 2){
            v = v * x;
        }
        return v;
    }
};

• 二进制快速幂

比如我们计算pow(3,5)，将5改写成二进制101，我们可以将算法过程写成以下形式：

class Solution {
public:
    double myPow(double x, int n) {
        double res = 1;
        long long b = n;
        if(n < 0){
            x = 1 / x;
            b = -b; //直接把int的负数取反会溢出，由于b的值只有int范围，所以不会溢出
        }
        while(b){
        	//当前位为1时，需要把这时的X计入结果
            if(b & 1){
                res *= x;
            }
            x *= x;//构造下一个乘积项：3^1,3^2,3^4,3^8,...
            b >>= 1;
        }
        return res;
    }
};

3. 超级次方

采用倒序遍历

class Solution {
public:
    int pow(int x, int n){
        int ans = 1;
        while(n){
            if(n % 2){
                ans = (long)ans * x % 1337;
            }
            x = (long)x * x % 1337;
            n >>= 1;
        }
        return ans;
    }
    int superPow(int a, vector<int>& b) {
        int result = 1;
        for(int i = b.size() - 1; i >= 0; --i){
            result = (long)result * pow(a, b[i]) % 1337;
            a = pow(a, 10);
        }
        return result;
    }
};