http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1114
1114: 平方根大搜索
Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 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++版：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cmath>
using namespace std;
int a1[],a2[],b[],c[],l1,l2,s[];
int l3,l4,l5,point,point2,point3,point1;
char ans[];
char ss[];
int chengfa()
{
int pos,i,j;
memset(s,,sizeof(s));
for (i=;i<=l4;i++)
for (j=,pos=i;j<=l4;j++)
s[pos++]+=a2[i]*a2[j];
pos-=;
for (i=;i<=pos;i++)
if (s[i]>=)
{
if (i==pos) pos++;
s[i+]+=s[i]/;
s[i]%=;
}
return pos;
}
void jia()
{
int p=,i;
if (point > point1)
{
for (i=;i<=point - point1;i++)
a2[p++]=a1[i];
int tt=;
for (i=point - point1+;i<=l1;i++)
a2[p++]=a1[i]+c[tt++];
point2=point;
}
else
{
for (i=;i<=point1-point;i++)
a2[p++]=c[i];
int tt=i;
for (i=;i<=l1;i++)
a2[p++]=a1[i]+c[tt++];
point2=point1;
}
int kk=;
p--;
for (i=;i<=p;i++)
{
a2[i]+=kk;
kk=a2[i]/;
a2[i]%=;
}
if (kk!=) a2[++p]=kk;
l4=p;
}
int gobj()
{
int sl=l5,bl=l2;
if (sl-point3>bl) return ;
else if (sl-point3<bl) return -;
while (sl> && bl>)
{
if (s[sl]>b[bl]) return ;
if (s[sl]<b[bl]) return -;
sl--;bl--;
}
if (sl==) return ;
else return ;
}
int main()
{
int T,n;
scanf("%d",&T);
while (T--)
{
memset(ans,,sizeof(ans));
memset(a1,,sizeof(a1));
memset(a2,,sizeof(a2));
memset(c,,sizeof(c));
memset(b,,sizeof(b));
scanf("%d",&n);
getchar();
scanf("%s",&ss);
int m=sqrt(n);
int mm=m;
int j=;
l1=;
point=;
while (mm)
{
a1[j++]=mm % ;
mm/=;
l1++;
}
point=;
mm=n;
j=;l2=;
while (mm)
{
b[j++]=mm%;
mm/=;
l2++;
}
c[]=;l3=;
int i;
for (i=;i<=;i++)
{
for (j=;j<=l3;j++)
c[j]*=;
int kk=;
for (j=;j<=l3;j++)
{
c[j]+=kk;
kk=c[j]/;
c[j]=c[j]%;
}
if (kk) c[++l3]=kk;
point1=i;
jia();
/*for (j=l4;j>0;j--)
{
if (point2==j) cout<<".";
printf("%d",a2[j]);
}
cout<<endl;*/
l5=chengfa(); //平方后长度
point3=*point2; //平方后小数点位置
/*for (j=l5;j>0;j--)
{
if (point3==j) cout<<".";
printf("%d",s[j]);
}
cout<<endl;*/
int re=gobj();
if (re==) //1:s>b -1:s<b
ans[i-]='';
else if (re==-)
{
ans[i-]='';
memset(a1,,sizeof(a1));
for (j=;j<=l4;j++)
a1[j]=a2[j];
l1=l4;
point=point2;
}
else break;
}
for (j=i;j<=;j++)
ans[i]='';
ans[]='\0';
//cout<<ans<<endl;
cout<<strstr(ans,ss) - ans << endl;
}
return ;
}
Java版：
import java.util.*;
import java.math.*;
public class Main {
static String tob(BigDecimal d)
{
String s=new String();
int n=;
while(!d.equals(BigDecimal.ZERO)&&n--!=)
{
d=d.multiply(BigDecimal.valueOf());
BigInteger x=d.toBigInteger();
s+=x;
d=d.subtract(BigDecimal.valueOf(x.longValue()));
}
return s;
}
public static BigDecimal culsqrt(int num)
{ return sqrtMathod(num); } public static BigDecimal sqrtMathod(int num)
{
BigDecimal sqrtNum = BigDecimal.valueOf(-);
boolean isFindSqrt = false; // get int sqrt num
double tempSqrt = ;
if (num > )
{
if (num == )
{
return BigDecimal.valueOf();
}
else
{
for (int j = ; j <= num / + ; j++)
{
if (j * j == num)
{
sqrtNum = BigDecimal.valueOf(j);
isFindSqrt = true;
break;
}
if (j * j > num)
{
tempSqrt = j - ;
break;
}
}
}
} if (!isFindSqrt)
{
sqrtNum = recuFindSqrt(num, BigDecimal.valueOf(tempSqrt), isFindSqrt, BigDecimal.valueOf());
} return sqrtNum;
} private static BigDecimal recuFindSqrt(int num, BigDecimal sqrtValue, boolean isFindSqrt, BigDecimal ac)
{
ac = ac.multiply(BigDecimal.valueOf());
BigDecimal tempSqrt = BigDecimal.valueOf();
for (int i = ; i < ; 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))==)
{
tempSqrt = sqrtValue.add(BigDecimal.valueOf(i - ) .divide( ac));
sqrtValue = tempSqrt;
break;
}
} BigDecimal temp = tempSqrt;
if (temp.toString().length() <= && !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--!=)
{
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);
System.out.println(tobs.indexOf(st));
}
}
}