Leetcode372

Leetcode372

 

 计算 3**15421过程如下:

3**15421=(3**1542)**10+3**1    //  3**1542=(3**154)**10+3**2      //  3**154= (3**15)**10+3*4         3**15=(3**1)**10+3**5
这样通过有限的操作次数就能完成计算 不需要计算一万多次

a*b%c    为 a%c * b%c

代码如下

 int MOD=1337;
    public int superPow(int a, int[] b) {
        return  dfs(a,b,b.length-1);
    }
    public int dfs(int a,int[] b,int index ){
        if(index==-1){
            return 1;
        }

        return pow(dfs(a, b, index - 1), 10) * pow(a, b[index]) % MOD;
    }
    //迭代版本的快速幂,快速幂件leetcode50
    int pow(int a,int  b){
        int res = 1;
        a=a%MOD;
        while(b>0){
            if((b&1)!=0){
                res = res * a%MOD;
            }
            a=a*a%MOD; 
            b>>=1;
        }
        return res;
    }

 

上一篇:poj 1663(水题)


下一篇:2021.11.6-测试