[数据结构与算法]每日一题 超级次方

372. 超级次方

做这道题的前提是掌握快速幂算法。其中需要知道乘法在取模的意义下满足分配律

(a?b) mod m=[(a mod m)?(b mod m)] mod m

举个🌰：如图

所以根据这个我们可以写出?

        a%=mod;
        int res = pow(a,b[0]);
        for(int i=1;i<b.size();i++){
            res = pow(res,10)*pow(a,b[i])%mod;
        }

?这里解释一下：res要初始化，所以先让res = pow(a,b[0])这样才能一层一层的求出最后的res。

刚开始的时候我先以为就这样就完了，但是这个pow( )函数还是需要自己去写。

力扣官方有详细解说「50. Pow(x, n) 的官方题解」。

快速幂 + 迭代

?

?

先放代码：

    int pow(int x,int n){
        int res = 1;
        while(n){
            if(n%2)
                res = (long)res*x%mod;
            x=(long)x*x%mod;
            n/=2;
        }
        return res;
    }

这段代码确实非常难理解，不过尝试代入一个例子，就容易理解一点。比如3^5 pow(3,5)过程如下：

?

大概意思是，如果遇到奇数 自身需要乘x。就像n=5的时候n/=2为2，少了一次方。

我的理解可能有误，如果有错欢迎提出。?

超级次方总体代码：

class Solution {
    const int mod = 1337;
public:
    int pow(int x,int n){
        int res = 1;
        while(n){
            if(n%2){
                res = res * x %mod;
            }
            x = x * x % mod;
            n /= 2;
        }
        return res;
    }
    int superPow(int a, vector<int>& b) {
        a%=mod;
        int res = pow(a,b[0]);
        for(int i=1;i<b.size();i++){
            res = pow(res,10)*pow(a,b[i])%mod;
        }
        return res;
    }
};