:type a: int :type b: List[int] :rtype: int
(self, a, b)
| 3 | self.base = 1337 |
| 4 | |
| 5 | def superPow(self, a, b): |
| 6 | """ |
| 7 | :type a: int |
| 8 | :type b: List[int] |
| 9 | :rtype: int |
| 10 | """ |
| 11 | # One knowledge: ab % k = (a%k)(b%k)%k |
| 12 | # a^1234567 % k = (a^1234560 % k) * (a^7 % k) % k = (a^123456 % k)^10 % k * (a^7 % k) % k |
| 13 | if b is None or len(b) == 0: |
| 14 | return 1 |
| 15 | last_digit = b.pop() |
| 16 | return self.powmod(self.superPow(a, b), 10) * \ |
| 17 | self.powmod(a, last_digit) % self.base |
| 18 | |
| 19 | def powmod(self, a, k): |
| 20 | a %= self.base |