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