372. Super Pow

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

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;
    }
}