CSU 1114 平方根大搜索 java大数

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

湖南省第八届大学生计算机程序设计竞赛

 1 import java.util.*;
 2 import java.math.*;
 3 
 4 public class Main {
 5 
 6     public static void main(String[] args) 
 7     {
 8         Scanner cin  = new Scanner(System.in);
 9         int T = cin.nextInt();
10         for(int t=1;t<=T;t++)
11         {
12             int num = cin.nextInt();
13             String str = cin.next();
14             
15             BigDecimal d = Sqrt(num);//sqrt(num),最多保存150位。
16             BigInteger x =d.toBigInteger();//取整数部分
17             d = d.subtract(BigDecimal.valueOf(x.longValue()));//保留小数部分
18             String hxl = Tostring(d);//将小数部分转化为二进制数字。
19             int tom = hxl.indexOf(str);//查找第一次出现的位置。
20             if(tom==-1) tom = 0;
21             System.out.println(tom);    
22         }
23     }
24 
25     private static String Tostring(BigDecimal d) 
26     {
27         /**
28          * 将小数部分转化为二进制数字。
29          * 每次乘2，取整数部分就可以。
30          * 长度最长为150.
31          * 如果数字太大会超时的。如果数字太小，会不精确。
32          */
33         String tom = new String();
34         int n = 150;
35         while(!d.equals(BigDecimal.ZERO)&& (n--)!=0)
36         {
37             d = d.multiply(BigDecimal.valueOf(2));
38             BigInteger x = d.toBigInteger();
39             tom+=x;
40             d = d.subtract(BigDecimal.valueOf(x.longValue()));
41         }
42         return tom;
43     }
44 
45     private static BigDecimal Sqrt(int num) {
46         /***
47          * 将整数num模拟开根号。
48          */
49         BigDecimal sqrtNum = BigDecimal.valueOf(0);
50         boolean isFindSqrt = false;
51         
52         int key = (int)Math.sqrt(num*1.0);
53         sqrtNum = BigDecimal.valueOf(key*1.0);
54         if(key*key == num) isFindSqrt = true;
55         if(!isFindSqrt)//不能刚好整除，调用函数，获得精确值。
56         {
57             sqrtNum = recuFindSqrt(num,BigDecimal.valueOf(key),
58                     isFindSqrt,BigDecimal.valueOf(1));
59         }
60         return sqrtNum;
61     }
62     private static BigDecimal recuFindSqrt(int num, BigDecimal sqrtValue,
63             boolean isFindSqrt, BigDecimal ac) {
64         /**
65          * 从每一位开始寻找，从0--9枚举。找最接近的点的方法。
66          * 暴力。(⊙o⊙)…
67          */
68         ac = ac.multiply(BigDecimal.valueOf(10));
69         BigDecimal tempSqrt = BigDecimal.valueOf(0);
70         
71         for(int i=0;i<10;i++)
72         {
73             tempSqrt = sqrtValue.add(BigDecimal.valueOf(i).divide(ac));
74             if(tempSqrt.multiply(tempSqrt).equals(BigDecimal.valueOf(num)))
75             {
76                 isFindSqrt = true;
77                 sqrtValue = tempSqrt;
78             }else if(tempSqrt.multiply(tempSqrt).compareTo(BigDecimal.valueOf(num))==1)
79             {
80                 tempSqrt = sqrtValue.add(BigDecimal.valueOf(i-1).divide(ac));
81                 sqrtValue = tempSqrt;
82                 break;
83             }
84         }
85         BigDecimal temp = tempSqrt;
86         if(temp.toString().length()<=150 && isFindSqrt==false)
87         {
88             sqrtValue = recuFindSqrt(num, tempSqrt, isFindSqrt, ac);
89         }
90         return sqrtValue;
91     }
92 }