// @Title: Pow(x, n) (Pow(x, n))
// @Author: qisiii
// @Date: 2022-02-20 14:51:34
// @Runtime: 0 ms
// @Memory: 40.3 MB
// @comment: 
// @flag: 
class Solution {
    public double myPow(double x, int n) {
        if(n == 0) return 1;
        if(n == 1) return x;
        if(n == -1) return 1 / x;
        double half = myPow(x, n / 2);
        double mod = myPow(x, n % 2);
        return half * half * mod;
    }
}

// @Title: Pow(x, n) (Pow(x, n))
// @Author: qisiii
// @Date: 2022-02-20 14:56:37
// @Runtime: 0 ms
// @Memory: 40.6 MB
// @comment: 模除作为结果
// @flag: BLUE
class Solution {
     public static double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == -1) {
            return 1 / x;
        }
        if (n == 1) {
            return x;
        }
        double v = myPow(x, n / 2);
        //模除不只有1和0，还有-1
        double mod = myPow(x, n % 2);
        return v*v*mod;
    }
}