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.
题目大意：
给定两个数 a, b，其中 b 会非常大，因此 b 用一个 int 的 的数组给出，然后求 (a^b\%1337)
初始思路1：
首先 ((a*b)\%M = ((a\%M)*(b\%M))\%M)，当数比较大的时候或者其乘积比较大的时候可以通过分开取模实现
第二个问题：由于数b非常大，因此可以分开求，利用二分求快速幂
第三个问题：数 b 的每一个数字存在一个数组中，因此可以模拟除法，从高位起，每次除以2，直到除完为止（每一位都为0为止）
代码如下：
class Solution {
public:
bool check(vector<int>&b)
{
int temp = 0;
for(int i = 0; i< b.size(); i+=1)
{
temp += (b[i]);
}
if(temp == 0)
return false;
else
return true;
}
int superPow(int a, vector<int>& b)
{
int ans = 1;
while(check(b))
{
if((b[b.size()-1]) & 1)
{
ans = ((ans % 1337) * (a % 1337)) % 1337;
}
a = ((a%1337) * (a%1337) % 1337);
for(int i = 0; i < b.size(); i += 1)
{
if((b[i] % 2 == 1) && (i != (b.size()-1)))
{
b[i+1] += 10;
}
b[i] >>= 1;
}
}
return ans;
}
};
这样的效果非常慢，结果980ms，勉强AC
优化思路：
从最后一位开始，每次处理一位，利用递归
(a^{1234567}\% k = (a^{1234560}\% k) * (a^7 \% k) \% k = (a^{123456} \% k)^{10} \% k * (a^7 \% k) % k)
假设 (f(a, b))计算 (a^b\%M)，则：
(f(a, 1234567)\%M =f(a, 1234560) * f(a, 7) \% M= (f(f(a, 123456), 10) * f(a, 7))\%M)
代码如下：
class Solution {
public:
int quick(int a, int b, int mod)
{
int ans = 1;
while(b)
{
if(b&1)
{
ans = (ans % mod) * (a % mod) % mod;
}
a = (a%mod) * (a % mod) % mod;
b >>= 1;
}
return ans;
}
int superPow(int a, vector<int>& b)
{
if(b.empty())
return 1;
int last_digit = b.back();
b.pop_back();
return (quick(superPow(a, b), 10, 1337) * quick(a, last_digit, 1337)) % 1337;
}
};
耗时8ms，快了很多
以上