[LeetCode] 372. Super Pow

 Problem: https://leetcode.com/problems/super-pow/

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        """
        
        a = Ak + B
        b = Ck + D
        
        a * b = (Ak + B) * (Ck + D) = ACk + ADk + BCk + BD
        
        (a * b) % k = (ACk + ADk + BCk + BD) % k = BD % k
        
        a % k = B
        b % k = D
        
        (a * b) % k = (a % k) * (b % k) % k
        
        (a ** b) % k = (a * a * a .. a) % k 
                     = (a % k) * (a % k) ... * (a % k) % k
                     = (a % k) ** b % k
                     
        (a % k) % k =  a % k
        
        for a = 2, b = [1, 0]
        
        result = (2 ** (1 * 10 + 0)) % 1337 
               = (2 ** (1*10) * 2 ** 0) % 1337
               = (2 ** 1 ** 10 % 1337) * (2 ** 0  % 1337) % 1337
               = ((2 % 1337) ** 10 % 1337) * ((2 % 1337) ** 0 % 1337) % 1337
        """
        
        if not b: return 1
        
        e = b.pop()
        
        return self.myPow(self.superPow(a, b), 10) * self.myPow(a, e) % 1337 
    
    
    def myPow(self, base, exp):
        result = 1
        base = base % 1337
        
        for i in range(exp):
            result = (result * base) % 1337
            
        return result