leetcode 372. Super Pow 快速幂实现+就这么办吧

淡淡的烟草味﹌ 2022-06-07 02:46 89阅读 0赞

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

这道题就是实现幂运算，但是不会做，网上看到了一个做法，很不错。

代码如下：

//快速幂，涉及到数学知识，不会做
    public class Solution
    {
        public int superPow(int a, int[] b)
        {
            if(a == 1 || b.length == 0)
                return 1;
            a = a % 1337;
            int[] nums = new int[11];
            int prev = 1,i = 0;
            while(i <= 10){
       //至于为什么是10，因为更多的话会浪费空间，更小的话，会增加递归层数，至于10是否最优，没有测量。
                nums[i++] = prev;
                prev = prev * a % 1337;
            }
    
            int[] divisor = new int[b.length - 1];
            int remainder = divide(b,10,divisor);
    
            return superPow(nums[10],divisor)*nums[remainder]%1337;
        }
    
        private int divide(int[] num,int baseNum,int[] divisor)
        {
            System.arraycopy(num,0,divisor,0,divisor.length);
    
            return num[num.length - 1];
        }
    }

下面是C++的做法

这道题题让我们求一个数的很大的次方对1337取余的值，开始一直在想这个1337有什么玄机，为啥突然给这么一个数，感觉很突兀，后来想来想去也没想出来为啥，估计就是怕结果太大无法表示，随便找个数取余吧。那么这道题和之前那道Pow(x, n)的解法很类似，我们都得对半缩小，不同的是后面都要加上对1337取余。由于给定的指数b是一个一维数组的表示方法，我们要是折半缩小处理起来肯定十分不方便，所以我们采用按位来处理，比如223 = (22)10 \* 23, 所以我们可以从b的最高位开始，算出个结果存入res，然后到下一位是，res的十次方再乘以a的该位次方再对1337取余

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        int superPow(int a, vector<int>& b) 
        {
            long long res = 1;
            for (int i = 0; i < b.size(); ++i) 
            {
                res = pow(res, 10) * pow(a, b[i]) % 1337;
            }
            return res;
        }
    
        int pow(int x, int n) 
        {
            if (n == 0) 
                return 1;
            if (n == 1) 
                return x % 1337;
            return pow(x % 1337, n / 2) * pow(x % 1337, n - n / 2) % 1337;
        }
    };