HDU6288缺失的数据范围

想用java写。

然后疯狂抽风的eclipse,调了两天也没调好，总是不输出中间结果？？？必须得所有输出结束后一起输出？？？

开一下eclipse,CPU高速运转，电脑也跟着抽风？？？

---

这一题，是一道二分，裸的。

BigInteger的类没有log取对数的接口。当然，可以选择手写，时间复杂度比较低，要敢写下来。

直接copy原博的代码

 

import java.util.*; import java.io.PrintWriter; import java.math.*; public class _6288_2 { static final BigInteger ONE = BigInteger.ONE; static final BigInteger TWO = new BigInteger("2"); public static void main(String[] args) { Scanner reader = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); int a, b; BigInteger k, low, top, mid, ans, v1, v2; int t = reader.nextInt(); while (t-- > 0) { a = reader.nextInt(); b = reader.nextInt(); k = reader.nextBigInteger(); top = k; low = ONE; ans = ONE; while (low.compareTo(top) <= 0) { mid = low.add(top).divide(TWO); v1 = mid.pow(a);// 变量1，n的a次方 int count = 1; BigInteger log = TWO; while (log.compareTo(mid) < 0) {// 求2的多少次方是n，并且向上取整 count++; log = log.multiply(TWO); } v2 = BigInteger.valueOf(count).pow(b);// 变量2，log2(n)的b次方 if (v1.multiply(v2).compareTo(k) <= 0) { if (ans.compareTo(mid) < 0) { ans = mid; } low = mid.add(ONE);// 向上二分 continue; } top = mid.subtract(ONE);// 向下二分 } out.println(ans); } out.close(); } }

吸取博主的二分精髓

//初始化 ans=1 low=1 top=k while low<=top     mid=(low+top)/2 res=v1*v2 //判断结果 if res<=k if ans<mid ans=mid low=mid+1 continue else top=mid-1

利用了一个ans来存储结果，有效的防止了最后不知道是low,mid,right哪一个大的问题。

值得思考。