湖南省第八届大学生程序设计大赛原题 D - 平方根大搜索 UVA 12505 - Searching in sqrt(n)
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=30746#problem/D
D - 平方根大搜索
UVA12505 - Searching in sqrt(n)
解题思路：求出n的平方根，去整数，化二进制，字符串子串查找。
基本思路简单，但是求平方根那里，不能直接用库函数方法，因为Math.sqrt()返回值的精度比较小。我们这里要用到的精度最高是140位。所以，求平方根的函数（中心代码转自http://blog.csdn.net/nujiah001/article/details/6657422）要自己写。不单只是自己写，由于设计的精度过高，一般的数据类型（如double）无法存储。所以必须用到JAVA中的大数类import java.math.BigDecimal;。
import java.util.*;import java.math.*;public class Main{static String tob(BigDecimal d) //求小数d的二进制表示，返回二进制存储串s{ String s=new String(); int n=150; while(!d.equals(BigDecimal.ZERO)&&n--!=0) { d=d.multiply(BigDecimal.valueOf(2)); BigInteger x=d.toBigInteger(); s+=x; d=d.subtract(BigDecimal.valueOf(x.longValue())); } return s;}public static BigDecimal culsqrt(int num) //以下三个函数（方法）用来求num的平方根{return sqrtMathod(num);}public static BigDecimal sqrtMathod(int num){BigDecimal sqrtNum = BigDecimal.valueOf(-1);boolean isFindSqrt = false;// get int sqrt numdouble tempSqrt = 0;if (num > 0){if (num == 1){return BigDecimal.valueOf(1);}else{for (int j = 0; j <= num / 2 + 1; j++){if (j * j == num){sqrtNum = BigDecimal.valueOf(j);isFindSqrt = true;break;}if (j * j > num){tempSqrt = j - 1;break;}}}}if (!isFindSqrt){sqrtNum = recuFindSqrt(num, BigDecimal.valueOf(tempSqrt), isFindSqrt, BigDecimal.valueOf(1));}return sqrtNum;}private static BigDecimal recuFindSqrt(int num, BigDecimal sqrtValue, boolean isFindSqrt, BigDecimal ac){ac = ac.multiply(BigDecimal.valueOf(10));BigDecimal tempSqrt = BigDecimal.valueOf(0);for (int i = 0; i < 10; i++){tempSqrt = sqrtValue .add(BigDecimal.valueOf(i).divide(ac) );if (tempSqrt .multiply(tempSqrt) .equals(BigDecimal.valueOf(num))){isFindSqrt = true;sqrtValue = tempSqrt;}else if (tempSqrt .multiply(tempSqrt) .compareTo(BigDecimal.valueOf(num))==1){tempSqrt = sqrtValue.add(BigDecimal.valueOf(i - 1) .divide( ac));sqrtValue = tempSqrt;break;}}BigDecimal temp = tempSqrt;if (temp.toString().length() <= 150 && !isFindSqrt){sqrtValue = recuFindSqrt(num, tempSqrt, isFindSqrt, ac);}return sqrtValue;}public static double add(double v1, double v2){BigDecimal b1 = new BigDecimal(Double.toString(v1));BigDecimal b2 = new BigDecimal(Double.toString(v2));return b1.add(b2).doubleValue();}public static void main(String[] args) {Scanner in= new Scanner(System.in);int t; int n; String st; t=in.nextInt(); while(t--!=0) { n=in.nextInt(); st=in.next(); BigDecimal d=culsqrt(n); //求平方根 BigInteger x=d.toBigInteger(); d=d.subtract(BigDecimal.valueOf(x.longValue())); //分离出小数部分 String tobs=tob(d); //将小数转化为二进制，存储在串tobs中 System.out.println(tobs.indexOf(st)); //输出查找结果 }}}
