Question
Formatted question description: https://leetcode.ca/all/372.html
372 Super Pow
Your task is to calculate: a^b mod 1337
where a is a positive integer and b is an extremely large positive integer given in the form of an array.
Example 1:
Input: a = 2, b = [3]
Output: 8
Example 2:
Input: a = 2, b = [1,0]
Output: 1024
Algorithm
Related maths
a^b % 1337 = (a%1337)^b % 1337
xy % 1337 = ((x%1337) * (y%1337)) % 1337
Reduced by half, the difference is that the remainder of 1337 is added. Since the given exponent b is a representation of a onedimensional array, it must be very inconvenient to deal with it if we halve it.
So we use bitwise processing, such as 2^23 = (2^2)^10 * 2^3
, so we can start from the highest bit of b, calculate a result and store it in res, and then go to the next bit , The tenth power of res is multiplied by the power of a and the remainder is 1337.
Code
Java

public class Super_Pow { class Solution { // 2^23 = (2^2)^10 * 2^3 public int superPow(int a, int[] b) { int res = 1; for (int i = 0; i < b.length; ++i) { res = pow(res, 10) * pow(a, b[i]) % 1337; } return res; } int pow(int x, int n) { if (n == 0) return 1; if (n == 1) return x % 1337; return pow(x % 1337, n / 2) * pow(x % 1337, n  n / 2) % 1337; } } }

Todo

class Solution(object): def superPow(self, a, b): """ :type a: int :type b: List[int] :rtype: int """ ret = 1 k = 1 for num in reversed(b): ret *= a ** (num) % 1337 a = a ** 10 % 1337 return ret % 1337