# 50. Pow(x, n)

<https://leetcode.com/problems/powx-n/description/>

## solution

* 快速幂: recursive
  * n为奇数，x^n = x(x^2)^(n//2)
  * n为偶数，x^n = (x^2)^(n//2)

```python
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:  # 退出递归的关键返回
            return 1
        if n < 0:
            return 1 / self.myPow(x, -n)
        if n % 2 == 1:
            return x * self.myPow(x, n - 1)
        return self.myPow(x * x, n // 2)  # 注意是 (x ** 2 ^ n//2) 而不是 (x ^ n//2 ^ 2)
```

时间复杂度：O(log(n))\
空间复杂度：O(1)

* 非递归: iterative

```python
# https://algo.monster/liteproblems/50

```

## follow up

[372. Super Pow](https://leetcode.com/problems/super-pow/description/)

```python
class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        mode = 1337
        ans = 1

        for i in b:
            ans = pow(ans, 10, mode) * pow(a, i, mode)
        return ans % mode
```

时间复杂度：O(n)\
空间复杂度：O(1)