動機

也是數學，(a*b) % c等於(a%c)*(b%c)

Problem

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.

 

Example 1:

Input: a = 2, b = [3]Output: 8

Example 2:

Input: a = 2, b = [1,0]Output: 1024

Example 3:

Input: a = 1, b = [4,3,3,8,5,2]Output: 1

Example 4:

Input: a = 2147483647, b = [2,0,0]Output: 1198

 

Constraints:

  • 1 <= a <= 231 - 1
  • 1 <= b.length <= 2000
  • 0 <= b[i] <= 9
  • b doesn't contain leading zeros.

Sol

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        a = a % 1337
        b = int(''.join([str(x) for x in b]))
        def pow(a,b):
            if b == 0:
                return 1
            if b == 1:
                return a
            else:
                if b%2 == 1:
                    ret = a*pow(a,b-1)
                else:
                    ret = pow(a,b//2)**2
                if ret > 1337:
                    ret = ret % 1337
                return ret
        return pow(a,b)