SuperPow

2017-06-09

问题描述

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:

a = 2
b = [3]
Result: 8

Example2:

a = 2
b = [1,0]
Result: 1024

思路

解法一：

最初的想法是利用 快速幂 的思想，由于指数特别大，所以在index >> 1这一步需要自己写一个大数的除2方法来代替。

大数除2代码如下：

string divide(string s){
        //大数除2
        string res = "";
        int rest = 0;
        int tmp = 0;
        if (s[0] == '1'){
            if (s.size() == 1){
                res = "0";
                return res;
            }
            rest = 1;
        }
        else{
            res += (s[0] - '0') / 2 + '0';
            rest = (s[0] - '0') % 2;
        }
        for (int i = 1; i < s.size(); i++){
            tmp = rest * 10 + (s[i] - '0');
            res += tmp / 2 + '0';
            rest = tmp % 2;
        }
        return res;
}

快速幂大致如下：

index是转化为string的大数指数。

long long sum = 1;
long long tmp = a;
while(index.compare("0") != 0){
    if ((index[index.size()-1] - '0') & 1){
        sum = (sum * tmp) % 1337;
    }
    tmp = (tmp * tmp) % 1337;
    index = divide(index);
}
return sum;

提交可以AC，然而时间是1400ms，有点爆炸。主要问题应该是在大指数除法的时候，时间开销太大。

解法二：

充分利用了数学上求余的性质：

$$
a^{b} mod m = (a mod m)^{b} mod m
$$

还有例如：

$$
a^{k} mod m = (a mod m)^{k-1} \times (a mod m)^1 mod m
$$

利用以上性质，我们可以预先算出$a^{0} 至 a^{9}$ 求余1337的余数，这可以大大加快后续的过程。

AC，时间只有12ms！！！

Code

解法一的代码在上面。

解法二：

int superPow2(int a, vector<int>& b)
{
    if (b.size() == 0) return 1;
    const int D = 1337;
    int A = a % D;
    vector<int> v(10, 0);
    //预先将A^0 ~ A^9 求余1337的结果算出存入v
    v[0] = 1;
    for (int i = 1; i < 10; i++)
    {
        v[i] = (v[i - 1] * A) % 1337;
    }
    int L = v[b[0]];
    for (int i = 1; i < b.size(); i++)
    {
        int M = 1;
        //指数乘以10的结果
        int j = 10;
        while(j != 0){
            if(j & 1){
                M = M * L % D;
            }
            L = L * L % D;
            j = j >> 1;
        }
        
        //乘以b当前位对应v数组中的余数值
        M = M*v[b[i]] % D;
        L = M;
    }
    return L;
}