在Java中使用二分查找查找M的第n个根

Question

我用java写了一个代码来求m的n次方根，其中n和m都是整数。1 <= n <= 30;1 <= m <= 10^9

如果根不是整数，那么我必须返回-1

我的代码适用于较小的m和n值，但对于n=6, m=4096则失败。我的代码返回-1，而正确的答案是4。我认为这是因为溢出在isProdGreater()方法。我怎样才能防止这种溢出呢?

public int NthRoot(int n, int m)
{
// code here
int l = 1, h = m;

int mid;
while(l<h){
mid = l + (h-l)/2;
//long prod = pow(mid,n);
if(isProdGreater(mid, n, m)){
h = mid;
}else{
l = mid+1;
}
}

if(l*l == m) return l;
return -1;
}

boolean isProdGreater(int x, int n, int target){
long a = 1;
for(int i=0; i<n; i++){

if(a*x >= target) return true;
a = a*x;
}
return false;
}

Answer 1

问题是你最后一次检查

if(l*l == m) return l;

这里检查的是平方，不是n次幂。你可能想要

if(Math.pow(l,n) == m) return l;