[LeetCode]Super Pow

题目描述:

LeetCode 372. Super Pow

Your task is to calculate ab 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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

暂无评论

张贴您的评论