372.-super-pow.md

372. Super Pow

• Medium

• 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.

Analysis

This is a problem that is highly based on math. So in math, we know that

• n1*n2 % 1337 == (n1 % 1337)*(n2 % 1337) % 1337
• If b = m*10 + d, we have a**b == (a**d)*(a**10)**m

Therefore we can use recursion to solve this problem.

class Solution(object):
    def superPow(self, a, b):
        if not b:
            return 1
        return pow(a, b.pop(), 1337)*self.superPow(pow(a, 10, 1337), b)%1337