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 one-dimensional 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

372 - Super Pow

Question

Algorithm

Code

All Problems

All Solutions