LeetCode 372. 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

描述

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

示例 1:

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

输出: 8

示例 2:

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

输出: 1024

思路

• 有以下运算法则
• ab\%k = a\%k \quad *\quad b\%k \quad \%kab%k=a%k∗b%k%k
• 我们从给定的 b 的最高位开始（数组编号是 0 的位置），计算出当前结果存入 res；
• 计算 b 的下一位时 num 时，先将 res 乘以 10 次方，再乘以给定 x 的 num 次方，再对 1337 取余。

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-06-27 20:41:08
# @Last Modified by:   何睿
# @Last Modified time: 2019-06-27 21:26:34
from typing import List
class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        res = 1
        for num in b:
            res = self.pow(res, 10) * self.pow(a, num) % 1337
        return res
    def pow(self, x: int, n: int) -> int:
        if n == 0:
            return 1
        if n == 1:
            return x % 1337
        return x**n % 1337

源代码文件在 这里 。