1114: 平方根大搜索
Time Limit: 5 Sec Memory Limit: 128 MB
Submit:
49 Solved: 23
[Submit][Status][Web
Board]
Description
在二进制中，2的算术平方根，即sqrt(2)，是一个无限小数1.0110101000001001111...
给定一个整数n和一个01串S，你的任务是在sqrt(n)的小数部分（即小数点之后的部分）中找到S第一次出现的位置。如果sqrt(n)是整数，小数部分看作是无限多个0组成的序列。
Input
输入第一行为数据组数T (T<=20)。以下每行为一组数据，仅包含一个整数n
(2<=n<=1,000,000)和一个长度不超过20的非空01串S。
Output
对于每组数据，输出S的第一次出现中，第一个字符的位置。小数点后的第一个数字的位置为0。输入保证答案不超过100。
Sample Input
2
2 101
1202 110011
Sample Output
2
58
HINT
Source
import java.util.*;
import java.math.*; public class Main { public static void main(String[] args)
{
Scanner cin = new Scanner(System.in);
int T = cin.nextInt();
for(int t=1;t<=T;t++)
{
int num = cin.nextInt();
String str = cin.next(); BigDecimal d = Sqrt(num);//sqrt(num),最多保存150位。
BigInteger x =d.toBigInteger();//取整数部分
d = d.subtract(BigDecimal.valueOf(x.longValue()));//保留小数部分
String hxl = Tostring(d);//将小数部分转化为二进制数字。
int tom = hxl.indexOf(str);//查找第一次出现的位置。
if(tom==-1) tom = 0;
System.out.println(tom);
}
} private static String Tostring(BigDecimal d)
{
/**
* 将小数部分转化为二进制数字。
* 每次乘2，取整数部分就可以。
* 长度最长为150.
* 如果数字太大会超时的。如果数字太小，会不精确。
*/
String tom = new String();
int n = 150;
while(!d.equals(BigDecimal.ZERO)&& (n--)!=0)
{
d = d.multiply(BigDecimal.valueOf(2));
BigInteger x = d.toBigInteger();
tom+=x;
d = d.subtract(BigDecimal.valueOf(x.longValue()));
}
return tom;
} private static BigDecimal Sqrt(int num) {
/***
* 将整数num模拟开根号。
*/
BigDecimal sqrtNum = BigDecimal.valueOf(0);
boolean isFindSqrt = false; int key = (int)Math.sqrt(num*1.0);
sqrtNum = BigDecimal.valueOf(key*1.0);
if(key*key == num) isFindSqrt = true;
if(!isFindSqrt)//不能刚好整除，调用函数，获得精确值。
{
sqrtNum = recuFindSqrt(num,BigDecimal.valueOf(key),
isFindSqrt,BigDecimal.valueOf(1));
}
return sqrtNum;
}
private static BigDecimal recuFindSqrt(int num, BigDecimal sqrtValue,
boolean isFindSqrt, BigDecimal ac) {
/**
* 从每一位开始寻找，从0--9枚举。找最接近的点的方法。
* 暴力。(⊙o⊙)…
*/
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==false)
{
sqrtValue = recuFindSqrt(num, tempSqrt, isFindSqrt, ac);
}
return sqrtValue;
}
}