LeetCode Super Pow

LeetCode Super Pow

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:

a = 2
b = [3]

Result: 8

Example2:

a = 2
b = [1,0]

Result: 1024

快速幂的进阶版,超级幂。要求a^B=a^{[b_0,b_1,b_2,...b_{n-1}]},其中的B用一个数组来表示,数组中的元素都是个位数,分别从高位到低位。比如第二个样例表示的是2^10

我一开始把a^B=a^{[b_0,b_1,b_2,...b_{n-1}]}展开成a^B=a^{b_0*10^{n-1}+b_1*10^{n-2}+...},对于每一项都用快速幂算出10^{n-i-1},然后用快速幂算出a^{b_i*10^{n-i-1}},最后累乘起来。但是很不幸WA或者TLE。

后来看了网上的题解,发现真是巧妙,这不就类似于多项式计算时层层嵌套的方法吗,一时想不起来那个叫什么名字了。比如我们要算a^{[b_0,b_1,b_2]},本来是a^{b_0*10^2+b_1*10+b_2}。但是我们计算是可以这样算,先算C_0=a^{b_0};递归到b_1时,在算到b_0的基础上,有C_1=(a^{b_0})^{10}*a^{b_1}=C_0^{10}*a^{b_1};递归到b_2时,有C_2=((a^{b_0})^{10}*a^{b_1})^{10}*a^{b_2}=C_1^{10}*a^{b_2}。把C_2展开其实就是a^{b_0*10^2+b_1*10+b_2}

完整代码如下:

typedef unsigned long long ull;

class Solution {
private:
	const static int MOD = 1337;
	ull fastPow(ull x, ull y) {
		ull ans = 1;
		while (y) {
			if (y & 1)ans = (ans*x) % MOD;
			y >>= 1;
			x = (x*x) % MOD;
		}
		return ans;
	}
public:
	int superPow(int a, vector<int>& b) {
		ull ans = 1;
		for (int i = 0; i < b.size(); ++i) {
			ans = fastPow(ans, 10)*fastPow(a, b[i]) % MOD;
		}
		return ans;
	}
};

本代码提交AC,用时9MS。

Leave a Reply

Your email address will not be published. Required fields are marked *