0372._Super_Pow.md

372. Super Pow

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/super-pow/description/

内容描述

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.

Example 1:

Input: a = 2, b = [3]
Output: 8
Example 2:

Input: a = 2, b = [1,0]
Output: 1024

解题方案

思路 1 - 时间复杂度: O(lgB)- 空间复杂度: O(1)******

递归

beats 22.60%

class Solution(object):
    def superPow(self, a, b):
        """
        :type a: int
        :type b: List[int]
        :rtype: int
        """
        def helper(a, b):
            if b == 1: 
                return a 
            if b & 1 == 0:
                tmp = helper(a, b // 2)
                return (tmp * tmp) % 1337
            else:
                tmp = helper(a, b // 2)
                return (tmp * tmp * a) % 1337
            
        if a == 0: return 0
        if a == 1: return 1
        b = int(''.join(map(str,b)))
        a %= 1337
        return helper(a, b) 

思路 2 - 时间复杂度: O(len(b))- 空间复杂度: O(1)******

数学方法，具体证明见ShuangQuanLi

这里 pow(x, y[, z]), 函数是计算x的y次方，如果z在存在，则再对结果进行取模，其结果等效于pow(x,y) %z

beats 100%

class Solution(object):
    def superPow(self, a, b):
        """
        :type a: int
        :type b: List[int]
        :rtype: int
        """
        return 0 if a % 1337 == 0 else pow(a, reduce(lambda x, y: (x * 10 + y) % 1140, b) + 1140, 1337)

自己重写了一下

class Solution(object):
    def superPow(self, a, b):
        """
        :type a: int
        :type b: List[int]
        :rtype: int
        """
        return 0 if a % 1337 == 0 else pow(a, int(''.join(map(str,b))) % 1140 + 1140) % 1337