力扣每日一题2021-12-05超级次方

超级次方


372.超级次方

题目描述

超级次方


思路

快速幂

Python实现

力扣每日一题2021-12-05超级次方

MOD = 1337
class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        def dfs(i):
            if i == -1:
                return 1
            return quickPow(dfs(i - 1), 10) * quickPow(a, b[i]) % MOD
        
        def quickPow(x, y):
            ans = 1
            x %= MOD
            while y:
                if y & 1:
                    ans = ans * x % MOD
                x = x * x % MOD
                y >>= 1
            return ans
        
        a %= MOD
        return dfs(len(b) - 1)

Java实现

力扣每日一题2021-12-05超级次方

class Solution {
    private static final int MOD = 1337;
    public int superPow(int a, int[] b) {
        return dfs(a % MOD, b, b.length - 1);
    }

    private int dfs(int a, int[] b, int idx) {
        if(idx == -1 || a == 1)
            return 1;
        return qPow(dfs(a, b, idx - 1),10) * qPow(a, b[idx]) % MOD;
    }

    private int qPow(int a, int b) {
        int ans = 1;
        a %= MOD;
        while(b > 0){
            if((b & 1) !=0)
                ans = ans * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return ans;
    }
}
上一篇:C#--运动控制05--日志显示(ListView和imageList控件使用)


下一篇:从今天开始刷算法题-2021.12.05