> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/math/super-pow.md).

# Super Pow

<https://leetcode.com/problems/super-pow/description/>

> Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

## Thoughts

<https://discuss.leetcode.com/topic/50489/c-clean-and-short-solution> 由于给的power是数组形式, 暗示我们要一位一位的处理. 由于ab % k = (a % k) (b % k) % k. 我们因此可以得到a ^ 1234567 % k = (a ^ 1234560 % k) *(a ^ 7 % k) % k. 即 f(a, \[1234567]) = f(f(a, \[123456]), 10)* f(a, 7) % k 也就是说我们每次把最后一位拆出来单独运算, 剩下的继续递归. 我们在算f(a, 7)时为了防止出现溢出, 不采用先连乘再mod的直观方法, 而是继续用我们刚提到的ab % k = (a % k) (b % k) % k.

## Code

```
class Solution {
    public int powMod(int a, int b, int k) {
        a %= k; // 防止res * a溢出  
        int res = 1;
        for (int i = 0; i < b; i++) {
            res = (res * a) % k; // 防止res * a溢出  
        }
        return res;
    }

    public int superPow(int a, int[] b, int bLen, int k) {
        if (bLen == 0) {
            return powMod(a, b[0], k);
        }

        return powMod(superPow(a, b, bLen - 1, k), 10, k) * powMod(a, b[bLen], k) % k;
    }

    public int superPow(int a, int[] b) {
        return superPow(a, b, b.length - 1, 1337);
    }
}
```

## Analysis

时间复杂度O(N), N为b长度, 一共要抛出N次, 每次要对抛出的那位计算一下pow, 由于最大才9次, 可以看作O(1), 还有powMod(superPow(a, b, bLen - 1, k), 10, k), 每位连乘十次, 也是O(1).


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/math/super-pow.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.