超级次方

372. 超级次方

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

示例 1：

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

示例 2：

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

示例 3：

输入：a = 1, b = [4,3,3,8,5,2]
输出：1

示例 4：

输入：a = 2147483647, b = [2,0,0]
输出：1198

提示：

1 <= a <= 2³¹ - 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b 不含前导 0

相似题目

Pow(x, n)

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int superPow(int a, vector<int>& b) { } };

python3 解法, 执行用时: 104 ms, 内存消耗: 15 MB, 提交时间: 2022-12-06 14:05:01

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337
        ans = 1
        for e in b:
            ans = pow(ans, 10, MOD) * pow(a, e, MOD) % MOD
        return ans

javascript 解法, 执行用时: 120 ms, 内存消耗: 47.1 MB, 提交时间: 2022-12-06 14:04:47

const MOD = BigInt(1337);
/**
 * @param {number} a
 * @param {number[]} b
 * @return {number}
 */
var superPow = function(a, b) {
    let ans = 1;
    for (const e of b) {
        ans = pow(BigInt(ans), 10) * pow(BigInt(a), e) % MOD;
    }
    return ans;
};

const pow = (x, n) => {
    let res = BigInt(1);
    while (n !== 0) {
        if (n % 2 !== 0) {
            res = res * BigInt(x) % MOD;
        }
        x = x * x % MOD;
        n = Math.floor(n / 2);
    }
    return res;
}

golang 解法, 执行用时: 8 ms, 内存消耗: 3.5 MB, 提交时间: 2022-12-06 14:04:21

const mod = 1337

func pow(x, n int) int {
    res := 1
    for ; n > 0; n /= 2 {
        if n&1 > 0 {
            res = res * x % mod
        }
        x = x * x % mod
    }
    return res
}

func superPow(a int, b []int) int {
    ans := 1
    for _, e := range b {
        ans = pow(ans, 10) * pow(a, e) % mod
    }
    return ans
}

java 解法, 执行用时: 5 ms, 内存消耗: 41.8 MB, 提交时间: 2022-12-06 14:04:07

class Solution {
    static final int MOD = 1337;

    public int superPow(int a, int[] b) {
        int ans = 1;
        for (int e : b) {
            ans = (int) ((long) pow(ans, 10) * pow(a, e) % MOD);
        }
        return ans;
    }

    public int pow(int x, int n) {
        int res = 1;
        while (n != 0) {
            if (n % 2 != 0) {
                res = (int) ((long) res * x % MOD);
            }
            x = (int) ((long) x * x % MOD);
            n /= 2;
        }
        return res;
    }
}

java 解法, 执行用时: 5 ms, 内存消耗: 41.8 MB, 提交时间: 2022-12-06 14:03:53

class Solution {
    static final int MOD = 1337;

    public int superPow(int a, int[] b) {
        int ans = 1;
        for (int i = b.length - 1; i >= 0; --i) {
            ans = (int) ((long) ans * pow(a, b[i]) % MOD);
            a = pow(a, 10);
        }
        return ans;
    }

    public int pow(int x, int n) {
        int res = 1;
        while (n != 0) {
            if (n % 2 != 0) {
                res = (int) ((long) res * x % MOD);
            }
            x = (int) ((long) x * x % MOD);
            n /= 2;
        }
        return res;
    }
}

javascript 解法, 执行用时: 164 ms, 内存消耗: 47.1 MB, 提交时间: 2022-12-06 14:03:39

const MOD = BigInt(1337);

/**
 * @param {number} a
 * @param {number[]} b
 * @return {number}
 */
var superPow = function(a, b) {
    let ans = BigInt(1);
    for (let i = b.length - 1; i >= 0; --i) {
        ans = ans * pow(BigInt(a), b[i]) % MOD;
        a = pow(BigInt(a), 10);
    }
    return ans;
};

const pow = (x, n) => {
    let res = BigInt(1);
    while (n !== 0) {
        if (n % 2 !== 0) {
            res = res * BigInt(x) % MOD;
        }
        x = x * x % MOD;
        n = Math.floor(n / 2);
    }
    return res;
}

golang 解法, 执行用时: 8 ms, 内存消耗: 3.5 MB, 提交时间: 2022-12-06 14:03:08

const mod = 1337

func pow(x, n int) int {
    res := 1
    for ; n > 0; n /= 2 {
        if n&1 > 0 {
            res = res * x % mod
        }
        x = x * x % mod
    }
    return res
}

func superPow(a int, b []int) int {
    ans := 1
    for i := len(b)-1; i >= 0; i-- {
        ans = ans * pow(a, b[i]) % mod
        a = pow(a, 10)
    }
    return ans
}

python3 解法, 执行用时: 108 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-06 14:02:27

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337
        ans = 1
        for e in reversed(b):
            ans = ans * pow(a, e, MOD) % MOD
            a = pow(a, 10, MOD)
        return ans

上一题

下一题

详情