记录编号	333674	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]大整数开方	最终得分	100
用户昵称	Mealy	是否通过	通过
代码语言	C++	运行时间	0.153 s
提交时间	2016-10-31 08:59:10	内存使用	0.19 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>


using namespace std;


const int nmax=286;


char ch[nmax];


class poi 
{
public:
	int s[nmax];
	
	
	void PreDo()
	{
		memset(s,0,sizeof(s));
	}
	
	void Carry()
	{
		for(int i=0;i<nmax;i++)
		{
			s[i+1]+=s[i]/10;
			s[i]%=10;
		}
	}
	
	
	poi operator + (const poi y) const 
	{
		poi ans;
		ans.PreDo();
		for(int i=0;i<nmax;i++)
		{
			ans.s[i]=s[i]+y.s[i];
		}
		ans.Carry();
		return ans;
	}
	
	
	poi operator * (const poi y) const
	{
		poi ans;
		ans.PreDo();
		for(int i=0;i<nmax/2;i++)
		{
			for(int j=0;j<nmax/2;j++)
			{
				ans.s[i+j]+=s[i]*y.s[j];
			}
		}
		ans.Carry();
		return ans;
	}
	
	
	poi operator / (const int y) const
	{
		poi ans;
		ans.PreDo();
		for(int i=nmax-1;i>=0;i--)
		{
			ans.s[i]+=s[i];
			ans.s[i-1]+=(ans.s[i]%y)*10;
			ans.s[i]=ans.s[i]/y;
		}
		ans.Carry();
		return ans;
	}
	
	
	poi Dec1()
	{
		for(int i=0;i<nmax;i++)
		{
			if(!s[i])
			{
				s[i]=9;
			}
			else
			{
				s[i]--;
				break;
			}
		}
		Carry();
	}
	
	
	bool operator < (const poi y) const
	{
		for(int i=nmax-1;i>=0;i--)
		{
			if(s[i]>y.s[i])
			{
				return 0;
			}
			if(s[i]<y.s[i])
			{
				return 1;
			}
		}
		return 0;
	}
		
	
	bool operator > (const poi y) const
	{
		for(int i=nmax-1;i>=0;i--)
		{
			if(s[i]<y.s[i])
			{
				return 0;
			}
			if(s[i]>y.s[i])
			{
				return 1;
			}
		}
		return 0;
	}
	
	
	void Read()
	{
		scanf("%s",ch);
		int len=strlen(ch);
		for(int i=0;i<len;i++)
		{
			s[len-i-1]=ch[i]-'0';
		}
	}
	
	
	void Out()
	{
		int n=nmax-1;
		while(!s[n])
		{
			n--;
		}
		for(int i=n;i>=0;i--)
		{
			printf("%d",s[i]);
		}
		printf("\n");
	}
	
}FJ;


bool Check(poi tmp)
{
	tmp=tmp*tmp;
	if(tmp>FJ)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}


void BiSearch()
{
	poi lft;
	lft.PreDo();
	
	
	poi rgt;
	rgt.PreDo();
	rgt.s[100]=1;
	
	
	poi mid;
	mid.PreDo();
	
	
	while(lft<rgt)
	{
		mid=lft+rgt;
		mid=mid/2;
		if(Check(mid))
		{
			rgt=mid;
		}
		else
		{
			lft=mid;
			lft.s[0]++;
			lft.Carry();
		}
	}
	if(Check(rgt))
	{
		lft.Dec1();
		lft.Out();
	}
	else
	{
		rgt.Dec1();
		rgt.Out();
	}
}

int main()
{
	freopen("hugeint.in","r",stdin);
	freopen("hugeint.out","w",stdout);
	FJ.PreDo();
	FJ.Read();
	BiSearch();
	return 0;
}