372.Super Pow

Tags: [math]

Link: https://leetcode.com/problems/super-pow/\#/description

Your task is to calculateabmod 1337 whereais a positive integer andbis an extremely large positive integer given in the form of an array.

Example1:

a = 2
b = [3]

Result: 8

Example2:

a = 2
b = [1,0]

Result: 1024

Solution: Math

class Solution(object):
    def superPow(self, a, b):
        """
        :type a: int
        :type b: List[int]
        :rtype: int
        """
        # base case
        if not b:
            return 1

        last_digit = b.pop()

        big_part = self.powmod(self.superPow(a, b), 10)
        small_part = self.powmod(a, last_digit)

        return (big_part * small_part) % 1337

    def powmod(self, a, p):
        # return a^p % 1337

        result = 1
        for _ in xrange(p):
            result *= a % 1337

        return result % 1337

Revelation:

• Knowledge: a*b % k = ((a%k) * (b%k)) % k.
• Knowledge: a^b % k = (a%k)^b % k.

Note:

• Time complexity = O(length of b).

Solution: Euler's theorem (欧拉定理)

Revelation:

• This problem also can be solved by Euler's theorem. What is Euler's theorem (欧拉定理), What is 费马定理(费马大定理， 费马小定理).