http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1114
1114: 平方根大搜索
Time Limit: 5 Sec Memory Limit: 128 MBSubmit: 118 Solved: 60
[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
分析;
数字比较大,开始打算用数组模拟,WA啦,后来想到用Java的BigDecimal类实现(可是还是没有实现,因为BigDecimal开根号不能实现,后来看别人用函数模拟了一个)。
AC代码:
C++版:
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <sstream> 5 #include <algorithm> 6 #include <cmath> 7 using namespace std; 8 int a1[10010],a2[10010],b[10000],c[10000],l1,l2,s[110000]; 9 int l3,l4,l5,point,point2,point3,point1; 10 char ans[1000]; 11 char ss[23]; 12 int chengfa() 13 { 14 int pos,i,j; 15 memset(s,0,sizeof(s)); 16 for (i=1;i<=l4;i++) 17 for (j=1,pos=i;j<=l4;j++) 18 s[pos++]+=a2[i]*a2[j]; 19 pos-=1; 20 for (i=1;i<=pos;i++) 21 if (s[i]>=10) 22 { 23 if (i==pos) pos++; 24 s[i+1]+=s[i]/10; 25 s[i]%=10; 26 } 27 return pos; 28 } 29 void jia() 30 { 31 int p=1,i; 32 if (point > point1) 33 { 34 for (i=1;i<=point - point1;i++) 35 a2[p++]=a1[i]; 36 int tt=1; 37 for (i=point - point1+1;i<=l1;i++) 38 a2[p++]=a1[i]+c[tt++]; 39 point2=point; 40 } 41 else 42 { 43 for (i=1;i<=point1-point;i++) 44 a2[p++]=c[i]; 45 int tt=i; 46 for (i=1;i<=l1;i++) 47 a2[p++]=a1[i]+c[tt++]; 48 point2=point1; 49 } 50 int kk=0; 51 p--; 52 for (i=1;i<=p;i++) 53 { 54 a2[i]+=kk; 55 kk=a2[i]/10; 56 a2[i]%=10; 57 } 58 if (kk!=0) a2[++p]=kk; 59 l4=p; 60 } 61 int gobj() 62 { 63 int sl=l5,bl=l2; 64 if (sl-point3>bl) return 1; 65 else if (sl-point3<bl) return -1; 66 while (sl>0 && bl>0) 67 { 68 if (s[sl]>b[bl]) return 1; 69 if (s[sl]<b[bl]) return -1; 70 sl--;bl--; 71 } 72 if (sl==0) return 0; 73 else return 1; 74 } 75 int main() 76 { 77 int T,n; 78 scanf("%d",&T); 79 while (T--) 80 { 81 memset(ans,0,sizeof(ans)); 82 memset(a1,0,sizeof(a1)); 83 memset(a2,0,sizeof(a2)); 84 memset(c,0,sizeof(c)); 85 memset(b,0,sizeof(b)); 86 scanf("%d",&n); 87 getchar(); 88 scanf("%s",&ss); 89 int m=sqrt(n); 90 int mm=m; 91 int j=1; 92 l1=0; 93 point=0; 94 while (mm) 95 { 96 a1[j++]=mm % 10; 97 mm/=10; 98 l1++; 99 } 100 point=0; 101 mm=n; 102 j=1;l2=0; 103 while (mm) 104 { 105 b[j++]=mm%10; 106 mm/=10; 107 l2++; 108 } 109 c[1]=1;l3=1; 110 int i; 111 for (i=1;i<=130;i++) 112 { 113 for (j=1;j<=l3;j++) 114 c[j]*=5; 115 int kk=0; 116 for (j=1;j<=l3;j++) 117 { 118 c[j]+=kk; 119 kk=c[j]/10; 120 c[j]=c[j]%10; 121 } 122 if (kk) c[++l3]=kk; 123 point1=i; 124 jia(); 125 /*for (j=l4;j>0;j--) 126 { 127 if (point2==j) cout<<"."; 128 printf("%d",a2[j]); 129 } 130 cout<<endl;*/ 131 l5=chengfa(); //平方后长度 132 point3=2*point2; //平方后小数点位置 133 /*for (j=l5;j>0;j--) 134 { 135 if (point3==j) cout<<"."; 136 printf("%d",s[j]); 137 } 138 cout<<endl;*/ 139 int re=gobj(); 140 if (re==1) //1:s>b -1:s<b 141 ans[i-1]='0'; 142 else if (re==-1) 143 { 144 ans[i-1]='1'; 145 memset(a1,0,sizeof(a1)); 146 for (j=1;j<=l4;j++) 147 a1[j]=a2[j]; 148 l1=l4; 149 point=point2; 150 } 151 else break; 152 } 153 for (j=i;j<=130;j++) 154 ans[i]='0'; 155 ans[130]='