372.md

372 Super Pow

Description

link

---

Solution

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

---

Code

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        if not b:
            return 1
        return pow(a, b.pop(), 1337) * self.superPow(pow(a, 10, 1337), b) % 1337