算法之快速幂

package com.zhang.reflection.面试.算法模版.快速幂;

public class QM {
    public static void main(String[] args) {
        System.out.println(quickM(10,9));
    }
    public static int quickM(int base,int power){
        int result=1;
        while(power>0){
            if(power%2==1){
                result=result*base;
                power=power/2;
                base=base*base;
            }else{
                power=power/2;
                base=base*base;
            }
        }
        return result;
    }
}

package com.zhang.reflection.面试.算法模版.快速幂;

/**
 * 你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
 */
public class QM1 {
    private static final int MOD=1337;
    public static void main(String[] args) {
        int a=2147483647;
        int[] b={2,0,0};
        System.out.println(superPow(a,b));
    }
    private static int superPow(int a,int[] b){
        return dfs(a%MOD,b,b.length-1);
    }
    private static int dfs(int a,int[] b,int idx){
        if(idx==-1||a==1){
            return 1;
        }
        return qPow(dfs(a,b,idx-1),10)*qPow(a,b[idx])%MOD;
    }
    private static int qPow(int a,int b){
        int result=1;
        a=a%MOD;
        while(b>0){
            if(b%2==1){
                result=result*a%MOD;
                b=b/2;
                a=a*a% MOD;
            }else{
                a=a*a%MOD;
                b=b/2;
            }
        }
        return result;
    }
}