如果更快的求一个整数k的n次方。如果两个整数相乘并得到结果的时间复杂度为O(1),得到整数k的N次方的过程请实现时间复杂度为O(logN)的方法。
给定k和n,请返回k的n次方,为了防止溢出,请返回结果Mod 1000000007的值。
测试样例:
2,3
返回:8
public int getPower(int k, int N) {
return (int)myGetPower((long)k,(long)N);
}
private long myGetPower(long base,long exp){
if(exp==0)return 1;
if(exp%2==0)return myGetPower((base*base)%1000000007,exp/2)%1000000007;
else return base*myGetPower((base*base)%1000000007,exp/2)%1000000007;
}