记录编号	262482	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]大整数开方	最终得分	100
用户昵称	GaoErFu	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-05-21 00:57:22	内存使用	0.00 MiB

#include<stdio.h>
#include<string.h>
void stbn(char *s,char *bn)
{
	int i,len=strlen(s);
	for(i=0;i<len;i++)
		bn[len-i]=s[i]-'0';
	bn[0]=len;
}
void add(char *a,char *b,char *c)
{
	int i,n;
	memset(c,0,220);
	n=a[0]>b[0]?a[0]:b[0];
	for(i=1;i<=n;i++){
		c[i]+=a[i]+b[i];
		c[i+1]=c[i]/10;
		c[i]%=10;
	}
	if(c[n+1])c[0]=n+1;
	else c[0]=n;
}
int sub(char *a,char *b,char *c)
{
	int i;
	memset(c,0,220);
	for(i=1;i<=a[0];i++){
		c[i]+=a[i]-b[i];
		if(c[i]<0){
			c[i]+=10;
			c[i+1]--;
		}
	}
	for(i=a[0];i>1;i--)
		if(c[i])break;
	c[0]=i;
	if(c[0]==1 && c[1]==1)return 1;
	else return 0;
}
int cmp(char *a,char *b)
{
	int i,n;
	if(a[0]!=b[0])return a[0]-b[0];
	for(i=a[0];i>0;i--)
		if(a[i]!=b[i])return a[i]-b[i];
	return 0;
}
void mul(char *a,char *b,char *c)
{
	int i,j;
	memset(c,0,220);
	for(i=1;i<=a[0];i++)
		for(j=1;j<=b[0];j++){
			c[i+j-1]+=a[i]*b[j];
			c[i+j]+=c[i+j-1]/10;
			c[i+j-1]%=10;
		}
	if(c[a[0]+b[0]]!=0)c[0]=a[0]+b[0];
	else c[0]=a[0]+b[0]-1;
}
void div(char *a,int b,char *c)
{
	int i,x=0;
	memset(c,0,110);
	for(i=a[0];i>0;i--){
		c[i]=(a[i]+x*10)/b;
		x=(a[i]+x*10)%b;
	}
	for(i=a[0];i>1;i--)
		if(c[i])break;
	c[0]=i;	
}
void print(char *a)
{
	int i;
	for(i=a[0];i>0;i--)
		printf("%d",a[i]);
	printf("\n");
}
int cc()
{
	freopen("hugeint.in","r",stdin);
	freopen("hugeint.out","w",stdout);
	char str[110]={0},a[110]={0},r1[110]={0},r2[110]={0},r[110]={0},tmp[220]={0};
	int c;
	scanf("%s",str);
	stbn(str,a);
	r1[0]=(a[0]+1)/2;
	r1[r1[0]]=1;	
	r2[0]=r1[0]+1;
	r2[r2[0]]=1;
	while(sub(r2,r1,tmp)!=1)	{
		add(r1,r2,tmp);
		div(tmp,2,r);
		mul(r,r,tmp);
		c=cmp(tmp,a);
		if(c==0){
			print(r);
			return 0;
		}
		else if(c>0)memcpy(r2,r,110);
		else memcpy(r1,r,110);
	}
	print(r1);
	return 0;
}
int gef=cc();
int main(){;
}