题目描述：

LeetCode 372. Super Pow

Your task is to calculate a^b mod 1337 where a is a positive integer and b is 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

题目描述：

计算a ^ b mod 1337的值。a是正整数，b是一个极大的正整数，以数组形式给出。

解题思路：

快速幂

Python代码：

class Solution(object):
    def superPow(self, a, b):
        """
        :type a: int
        :type b: List[int]
        :rtype: int
        """
        ans, pow = 1, a
        for n in b[::-1]:
            ans = (ans * (pow ** n) % 1337) % 1337
            pow = (pow ** 10) % 1337
        return ans

优化的快速幂

Python代码：

class Solution(object):
    def superPow(self, a, b):
        """
        :type a: int
        :type b: List[int]
        :rtype: int
        """
        ans, pow = 1, a
        for n in b[::-1]:
            ans = (ans * self.quickPow(pow, n, 1337)) % 1337
            pow = self.quickPow(pow, 10, 1337)
        return ans

    def quickPow(self, a, b, m):
        ans = 1
        while b > 0:
            if b & 1: ans *= a
            a = (a * a) % m
            b >>= 1
        return ans

 

本文链接：http://bookshadow.com/weblog/2016/07/07/leetcode-super-pow/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码