记录编号	334395	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]大整数开方	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.969 s
提交时间	2016-10-31 21:46:58	内存使用	0.32 MiB

#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<stack>
#include<cstdio>
#define LL long long
#define Begin freopen("hugeint.in","r",stdin);freopen("hugeint.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
using namespace std;
const int maxn=1010;
struct Bigint{
	int a[maxn];
	void Print(){
		for(int i=a[0];i>=1;i--)printf("%d",a[i]);
		puts("");
	}
	void Init(string s){
		memset(a,0,sizeof(a)); 
		a[0]=s.size();
		for(int i=1;i<=a[0];i++)a[i]=s[a[0]-i]-'0';
		while(a[0]>1 && a[a[0]]==0)a[0]--;
	}
	Bigint operator + (const Bigint & b)const{
		Bigint c;memset(c.a,0,sizeof(c.a));
		c.a[0]=max(a[0],b.a[0]);
		for(int i=1;i<=c.a[0];i++){
			c.a[i]+=a[i]+b.a[i];
			if(c.a[i]>9){
				c.a[i+1]++;
				c.a[i]-=10;
			}
		}
		if(c.a[c.a[0]+1])c.a[0]++;
		return c;
	}
	Bigint operator - (const Bigint & b)const{
		Bigint c;memset(c.a,0,sizeof(c.a));
		c.a[0]=max(a[0],b.a[0]);
		for(int i=1;i<=c.a[0];i++){
			c.a[i]+=a[i]-b.a[i];
			if(c.a[i]<0){
				c.a[i+1]--;
				c.a[i]+=10;
			}
		}
		while(c.a[0]>1 && c.a[c.a[0]]==0)c.a[0]--;
		return c;
	}
	Bigint operator * (const Bigint & b)const{
		Bigint c;memset(c.a,0,sizeof(c.a));
		c.a[0]=a[0]+b.a[0]-1;
		for(int i=1;i<=a[0];i++){
			for(int j=1;j<=b.a[0];j++){
				c.a[i+j-1]+=a[i]*b.a[j];
				if(c.a[i+j-1]>9){
					c.a[i+j]+=c.a[i+j-1]/10;
					c.a[i+j-1]%=10;
				}
			}
		}
		if(c.a[c.a[0]+1])c.a[0]++;
		while(c.a[0]>1 && c.a[c.a[0]]==0)c.a[0]--;
		return c;
	}
	bool operator < (const Bigint & b)const{
		if(a[0]<b.a[0])return true;
		if(a[0]>b.a[0])return false;
		for(int i=a[0];i;i--){
			if(a[i]>b.a[i])return false;
			if(a[i]<b.a[i])return true;
		}
		return false;
	}
	bool operator == (const Bigint & b)const{
		if(a[0]^b.a[0])return false;
		for(int i=a[0];i;i--)if(a[i]^b.a[i])return false;
		return true;
	} 
	bool operator > (const Bigint & b)const{
		if(a[0]<b.a[0])return false;
		if(a[0]>b.a[0])return true;
		for(int i=a[0];i;i--){
			if(a[i]>b.a[i])return true;
			if(a[i]<b.a[i])return false;
		}
		return false;
	}
};
Bigint numcpy(const Bigint p,int pos){//从pos开始的地方复制p数组到q数组 
	Bigint a;memset(a.a,0,sizeof(a.a));
	for(int i=1;i<=p.a[0];i++)a.a[i+pos-1]=p.a[i];
	a.a[0]=p.a[0]+pos-1;
	return a;
} 
Bigint operator / (Bigint & a,Bigint & b){
	Bigint c;memset(c.a,0,sizeof(c.a));
	if(a==b){c.Init("1");return c;} 
	if(a<b){c.Init("0");return c;}
	c.a[0]=a.a[0]-b.a[0]+1;
	for(int i=c.a[0];i>0;i--){
		Bigint temp=numcpy(b,i);
		while(a>temp || a==temp){c.a[i]++;a=a-temp;}
	}
	while(c.a[0]>1 && c.a[c.a[0]]==0)c.a[0]--;
	return c;
}
Bigint operator % (Bigint & a,Bigint & b){
	Bigint c;memset(c.a,0,sizeof(c.a));
	if(a==b){c.Init("0");return c;} 
	if(a<b)return a;
	c.a[0]=a.a[0]-b.a[0]+1;
	for(int i=c.a[0];i>0;i--){
		Bigint temp=numcpy(b,i);
		while(a>temp || a==temp){
			c.a[i]++;
			a=a-temp;
		}
	}
	return a;
}
void Init();
int main(){
    Begin;
    Init();
    getchar();getchar();
    End;
    return 0;
}
void Init(){
	Bigint a;
	string s;cin>>s;
	a.Init(s);
	Bigint l,r;l.Init("0");r.Init(s);
	Bigint haha;haha.Init("2");
	Bigint yi;yi.Init("1");
	Bigint mid;
	while(l<r || l==r){
		mid=l+r;mid=mid/haha;
		Bigint ans;ans=mid*mid;
		if(ans==a){
			mid.Print();return;
		}
		if(ans<a)l=mid+yi;
		else r=mid-yi;
	}
	r.Print();
}