Leetcode_372_超级次方_hn

2020-03-21 本文已影响0人 1只特立独行的猪

题目描述

你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

示例

示例 1：

输入: a = 2, b = [3]
输出: 8

示例2：

输入: a = 2, b = [1,0]
输出: 1024

解答方法

方法一：快速幂+先对每个因子求模，然后对因子相乘的结果求模

思路

快速幂：

首先明确问题：现在 b 是一个数组，不能表示成整型，而且数组的特点是随机访问，删除最后一个元素比较高效。

不考虑求模的要求，以 b = [1,5,6,4] 来举例，结合指数运算的法则，我们可以发现这样的一个规律：
$\begin{aligned} &a^{[1,5,6,4]} \\ =& a^{4} \times a^{[1,5,6,0]} \\ =& a^{4} \times (a^{[1,5,6]})^{10} \end{aligned}$
用递归

mod运算

(a * b) % k = (a % k)(b % k) % k
对乘法的结果求模，等价于先对每个因子都求模，然后对因子相乘的结果再求模。
参考：https://leetcode-cn.com/problems/super-pow/solution/you-qian-ru-shen-kuai-su-mi-suan-fa-xiang-jie-by-l/

代码

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        if len(b)==0:
            return 1
        part1 = pow(a,b.pop())
        part2 = pow(self.superPow(a,b),10)
        return (part1*part2) % 1337

时间复杂度

O(N)，N 为 b 的长度。