# 湖南第八届大学生程序设计大赛原题 D - 平方根大搜索 UVA 12505 - Searching in sqrt(n)

www.MyException.Cn  网友分享于：2013-09-10  浏览：28次

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=30746#problem/D

D - 平方根大搜索

UVA12505 - Searching in sqrt(n)

 1545839 20114045007 D Accepted 125440 KB 5044 ms Java 2593 B 2013-09-09 14:35:32

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 num
double 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++)
{
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));
}

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));  //输出查找结果
}
}
}