题目描述

计算$a^b mod 1337$，a是正整数，b是一个用array表示的大整数。

样例

Example 1:

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



Example 2:

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

算法1

(快速幂) $O(log N)$

首先，利用数论里的

设       a1 = a mod c,  b1 = b mod c,

那么  (a * b) mod c   =   [(nc+a1) * (mc+b1)] mod c
                    =   (a1 * b1) mod c

所以 (a * b) mod c = (a mod c) * (b mod c) mod c

可以得到
$a^{b_{n-1}…b_1b_0} \% c = (a^{b_{n-1}…b_1}^{10} \% c) * (a^{b_0} \% c) \%c $

例如

$ a^{123} \% c = (a^{120} \% c) * (a^3 \% c) %c = ((a^{12} \% c)^{10} \% c) * (a^3 \% c) \% c $

相关：快速幂算法模板by yxc

int qmi(int m, int k, int p)
{
    int res = 1, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

C++ 代码

class Solution {
public:
    int superPow(int a, vector<int>& b) {
        if (b.empty()) return 1;
        int last_digit = b.back(); //取出b=123的最后一位3
        b.pop_back(); //b从123变成12
        return pow(superPow(a, b), 10) * pow(a, last_digit) % base; // a^123 %c = ((a^12)^10 % c) * (a^3 % c) % c
    }
    const int base = 1337;

    int pow(int a, int b) //a^b mod 1337 where 0 <= b <= 10
    {
        a %= base;
        int res = 1;
        for (int i = 0; i < b; ++i) res = (res * a) % base; //最多计算10次
        return res;
    }

};