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

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath> 
#define maxn 200
using namespace std;
char ch[maxn];
class big{
public:
	int s[200];
	void init(){
		memset(s,0,sizeof(s));
	}
	void carry(){
		for (int i=0;i<maxn;i++){
			s[i+1]+=s[i]/10;
			s[i]=s[i]%10;
		}
	}
	big add(big b){
		big c; c.init();
		for (int i=0;i<maxn;i++){
			c.s[i]=b.s[i]+s[i];
		}
		c.carry();
		return c;
	}
	big div2(){
		big c; c.init();
		for (int i=maxn-1;i>=0;i--){
			c.s[i]+=s[i];
			c.s[i-1]+=(c.s[i]%2)*10;
			c.s[i]=c.s[i]/2;
		}
		c.carry();
		return c;
	}
	big sqr(){
		big c; c.init();
		for (int i=0;i<maxn/2;i++){
			for (int j=0;j<maxn/2;j++){
				c.s[i+j]+=s[i]*s[j];
			}
		}
		c.carry();
		return c;
	}
	void write(){
		int n=maxn-1;
		while(n){
			if (s[n]) break;
			n--;
		}
		for (int i=n;i>=0;i--){
			printf("%d",s[i]);
		}
		printf("\n");
	}
	void read(){
		scanf("%s",ch);
		int m=strlen(ch);
		init();
		for (int i=0;i<m;i++){
			s[m-i-1]=ch[i]-'0';
		}
	}
	void dec(){
		for (int i=0;i<maxn;i++){
			if (!s[i]) s[i]=9;
			else {
				s[i]--;
				break;
			}
		}
	}
	bool operator < (const big b)const{
		for (int i=maxn-1;i>=0;i--){
			if (s[i]>b.s[i]) return 0;
			if (s[i]<b.s[i]) return 1;
		}
		return 0;
	}
	big operator + (const big b) const{
		big c; c.init();
		for (int i=0;i<maxn;i++){
			c.s[i]=b.s[i]+s[i];
		}
		c.carry();
		return c;
	}
}t;
void lower_bound(){
	big l; l.init();
	big r; r.init(); r.s[50]=1;
	big mid; mid.init();
//	t.write();
	while(l<r){
		mid=l+r;
		mid=mid.div2();
//		mid.write();
//		mid.sqr().write();
		if (t<mid.sqr()){
			r=mid;
		}
		else{
			l=mid;
			l.s[0]++; l.carry();
		}
	}
	l.dec();
	l.write();
}
int main(){
	freopen("hugeint.in","r",stdin);
	freopen("hugeint.out","w",stdout);
	t.read();
	lower_bound();
	return 0;
}