如何高效进行模幂运算 :: labuladong的算法小抄

[labuladong]

文章链接点这里：如何高效进行模幂运算

评论礼仪 见这里，违者直接拉黑。

[JohanRain]

可以提一下欧拉定理

[zhongweiLeex]

由于 java 版本题目给的形参列表是 int[] 所以，需要有点小调整，但是还是使用的是东哥提供的思路。

class Solution {
    int base = 1337;
    public int superPow(int a, int[] b) {
        return superP(a,b,b.length);
    }
    private int superP(int a, int[] b, int len){
        if(len == 0) return 1;
        int last = b[len-1];
        len--;
        //拆分 成两个部分 一个部分是将数组末尾的数字计算取模
        //另一个是将剩余的 还有个10次方取模
        int part1 = myPow(a,last);
        int part2 = myPow(superP(a,b,len),10);
        return (part2*part1)%base;
    }
    //求 a^b 对 base取模的结果
    private int myPow(int a, int b){
        if(b==0) return 1;
        a = a%base;

        if(b%2 == 1){
            return (a*myPow(a,b-1))%base;
        }else{
            int sub = myPow(a,b/2);
            return (sub*sub)%base;
        }
    }
}

[xlintime]

js

var superPow = function(a, b) {
    let BASE=1337;
     if(b.length===0){
         return 1;
     }
    let last= b.pop()
    let part1=myPow(a,last);
    let part2=myPow(superPow(a,b),10);
    return  (part1*part2)%BASE //这里还要求一次

     function myPow(a,k){ // 求模
           let res=1;
           a%=BASE;//  先自己砍一刀
           for(let i=0;i<k;i++){
              res*=a; // 和自身相乘
              res%=BASE // 再求一次模
           }
           return res
     }
};

[dreamyang-liu]

Java + 快速幂

class Solution {
    int MOD = 1337;
    public int pow(int base, int exp) {
        base = base % MOD;
        int prod = 1;
        while(exp > 0) {
            if((exp & 1) == 1) {
                prod *= base;
                prod %= MOD;
            }
            base *= base;
            base %= MOD;
            exp >>= 1;
        }
        return prod;
    }
    
    public int superPow(int a, LinkedList<Integer> b) {
        if(b.size() == 0) return 1;
        int pow1 = pow(a, b.getLast());
        b.removeLast();
        int pow2 = pow(superPow(a, b), 10);
        return (pow1 * pow2) % MOD;
    }
    
    public int superPow(int a, int[] b) {
        LinkedList<Integer> c = new LinkedList<>();
        for(int be:b) c.add(be);
        return superPow(a, c);
    }
}

[deepbreath373]

check in

[GithubMingEnter]

class Solution {
    int base=1337;
public:
    int fastPow(int fbase, int power){
        if(power==0) return 1;
        int res=1;
        
        if(power%2==1){
            return  (fastPow(fbase%base,power-1)*(fbase%base))%base;
        }
        else{
              res=fastPow((fbase%base), power/2);
            return  (res*res)%base;
        }
        
    }
    int superPow(int a, vector<int>& b) {
        if(b.empty()){
            return 1;
        }
        int po=b.back();
        b.pop_back();
        int n1=fastPow(a,po);
        int n2=fastPow(superPow(a,b),10);

        return (n1*n2)%base;
    }
};

C++代码

[char8x]

对于50题，补充了处理幂是负数的情况

const myPow = function (x, n) {
  if (n == 0) return 1;

  if (n < 0) {
    return 1 / myPow(x, Math.abs(n));
  } else if (n % 2 === 1) {
    return x * myPow(x, n - 1);
  } else {
    const sub = myPow(x, n / 2);
    return sub * sub;
  }
};