Improvement of @ShuangquanLi's solution, with full proof of the math theorem.

• The math statement is the following:
For any positive integer n and a, let phi(n) be the Euler number of n,
pow(a, n) = pow(a, n-phi(n)) mod n.
The proof: Let n be equal to the product of n_1, n_2, ..., n_k for each n_i a power of distinct primes p_i. By Chinese Remainder's Theorem, it suffices to show that pow(a, n) and pow(a, n- phi(n)) are equal mod each n_i.
If a is coprime to n_i, this follows from Euler's theorem a^phi(n_i) = 1 mod n_i and phi(n_i) divides phi(n).
If a is some power of p_i, I claim both sides are zero mod n_i.
Consider the inequality r <= 2^(r-1) <= p_i^(r-1) for any positive integer r.
Suppose n_i = pow(p_i, r), then n >= n - phi(n) >= n_i - phi(n_i) = p_i^(r-1) >= r.
Let delta = n - phi(n). We rewrite the equality as
pow(a, delta + phi(n))= pow(a, delta) mod n.
The conclusion is as long as b is greater than the delta, we can throw away any multiple of phi(n).
Therefore, the only improvement below is to add phi when the remainder y is less than delta. It doesn't impact the performance much, but theoretically cleaner. The time is under 2ms.

``````public class Solution {
private final int m = 1337;
private final int phi = 1140;
private final int delta = m - phi;
private int myPow(int x, int y) {
int ret = 1;
x %= m;
while (y > 0) {
if ((y&1) == 1) ret *= x;
ret %= m;
y >>= 1;
x = x*x % m;
}
return ret;
}

public int superPow(int a, int[] b) {
a %= m;
if (a == 0) return 0;
int y = 0;
for (int i : b) y = (y*10 + i) % phi;
if (y < delta) y += phi;         // make sure the remainder is greater than delta.
return myPow(a, y);
}
}
``````
• @param a any pos * @param b the power
• @return pow(a,b) = pow(a,y) mod m
*/

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.