ID | Title | Difficulty | |
---|---|---|---|
Loading... |
372. Super Pow
Medium
LeetCode
Math, Divide and Conquer
Problem
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.
Example 1:
Input: a = 2, b = [3]
Output: 8
Example 2:
Input: a = 2, b = [1,0]
Output: 1024
Example 3:
Input: a = 1, b = [4,3,3,8,5,2]
Output: 1
Code
https://zh.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic
模的加法: (A + B) mod C = (A mod C + B mod C) mod C
模的减法: (A - B) mod C = (A mod C - B mod C) mod C
模的乘法: (A * B) mod C = (A mod C * B mod C) mod C
模的指数: A^B mod C = ( (A mod C)^B ) mod C
class Solution {
public int superPow(int a, int[] b) {
if(b == null || b.length == 0) return 1;
return
powMod1337(
superPow(a, Arrays.copyOf(b, b.length - 1)),
10
)
*
powMod1337(
a,
b[b.length - 1]
)
% 1337;
}
private int powMod1337(int a, int b){
if(b == 0) return 1;
return ((a % 1337) * powMod1337(a, b - 1)) % 1337;
}
}
按 <- 键看上一题!
371. Sum of Two Integers
按 -> 键看下一题!
373. Find K Pairs with Smallest Sums