Java二分查找求M的N次整数根时isProdGreater方法溢出怎么解决

1 直接错误：最终校验逻辑写错 #

你当前代码在二分结束后，使用l*l == m做校验，这是平方根的判断逻辑，对n≠2的场景完全不适用。比如你测试的用例n=6、正确结果l=4时，4*4=16≠4096，自然会错误返回-1，这是本次测试失败的首要原因。

2 溢出问题修复 #

isProdGreater方法的溢出可以通过提前做除法判断避免：每次相乘前先判断a > target / x，如果成立，说明a*x必然大于target，不用实际执行乘法，从根源避免溢出。

修复后完整代码 #

public int NthRoot(int n, int m) {
    // 边界情况特殊处理
    if (m == 1) return 1;
    // 优化右边界：1e5的2次方已经大于1e9，不需要到m
    int l = 1, h = Math.min(m, 100000);
    
    while(l < h){
        int mid = l + (h - l)/2;
        if(isProdGreater(mid, n, m)){
            h = mid;
        }else{
            l = mid + 1;
        }
    }
    // 最终校验l的n次方是否正好等于m
    return isExactRoot(l, n, m) ? l : -1;
}

// 判断x^n是否大于等于target，无溢出
boolean isProdGreater(int x, int n, int target){
    long a = 1;
    for(int i = 0; i < n; i++){
        // 提前判断，避免乘法溢出
        if(a > target / x){
            return true;
        }
        a = a * x;
        if(a >= target){
            return true;
        }
    }
    return false;
}

// 校验x^n是否严格等于target
boolean isExactRoot(int x, int n, int target){
    long res = 1;
    for(int i = 0; i < n; i++){
        res = res * x;
        if(res > target){
            return false;
        }
    }
    return res == target;
}

内容的提问来源于stack exchange，提问作者kakashiOfSharingan