leetcode Super Pow

leetcode Super Pow

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.

Example1:
1
2
3
4
a = 2
b = [3]

Result: 8
Example2:
1
2
3
4
a = 2
b = [1,0]

Result: 1024

题目地址：leetcode Super Pow

题意：给定数a和用数组表示的一个很大的数b，求a^b % 1337

思路：

一个数e可以写成如下形式： \[ e=\sum _{i=0}^{n-1}a_{i}2^{i} \]

显然，对于b的e次方，有：

\[ b^{e}=b^{\left(\sum _{i=0}^{n-1}a_{i}2^{i}\right)}=\prod _{i=0}^{n-1}\left(b^{2^{i}}\right)^{a_{i}} \]

\[ c\equiv \prod _{i=0}^{n-1}\left(b^{2^{i}}\right)^{a_{i}}\ ({\mbox{mod}}\ m) \]

此外，还有：

c mod m = (a ⋅ b) mod m = [(a mod m) ⋅ (b mod m)] mod m

参照wiki :https://en.wikipedia.org/wiki/Modular_exponentiation

看懂了上面的式子后，回到此题，此题b用数组表示，其实就是把上面的数e的2改为10即可。

因此，用Python可以得到此题的写法为：

class Solution(object):
    def superPow(self, a, b):
        """
        :type a: int
        :type b: List[int]
        :rtype: int
        """
        ans = 1
        mod = 1337
        for bi in b[::-1]:
            ans = ans * a ** bi % mod
            a = a ** 10 % mod
        return ans

当然，我们可以用快速幂来加速

C++

class Solution {
private:
	int mod = 1337;
public:
	int superPow(int a, vector<int>& b) {
		int n = b.size();
		int ans = 1;
		for (int i = n - 1; i >= 0; i--) {
			ans = ans * quick_pow(a, b[i]) % mod;
			a = quick_pow(a, 10);
		}
		return ans;
	}
	inline int quick_pow(int a, int b) {
		int ans = 1;
		a %= mod;
		while (b > 0) {
			if (b & 1) ans = ans * a % mod;
			a = a * a %mod;
			b >>= 1;
		}
		return ans;
	}
};

Java

public class Solution {
    private int mod = 1337;
    public int superPow(int a, int[] b) {
        int n = b.length;
		int ans = 1;
		for (int i = n - 1; i >= 0; i--) {
			ans = ans * quick_pow(a, b[i]) % mod;
			a = quick_pow(a, 10);
		}
		return ans;
	}
	
	int quick_pow(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;
	
    }
}

本题是leetcode 372 Sum of Two Integers 题解

更多题解可以查看：https://www.hrwhisper.me/leetcode-algorithm-solution/