记录编号	436661	评测结果	TTTTTTTTTT
题目名称	[NOIP 2011]大整数开方	最终得分	0
用户昵称	+1s	是否通过	未通过
代码语言	C++	运行时间	10.000 s
提交时间	2017-08-12 10:47:46	内存使用	0.31 MiB

#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("hugeint.in");
ofstream fout("hugeint.out");
struct hugeint {
	int data[110];
	int len;
};
int huge_cmpr(hugeint a,hugeint b) {
	if(a.len>b.len)return 1;
	if(a.len<b.len)return -1;
	for(int i=a.len-1; i>=0; i--) {
		if(a.data[i]>b.data[i])return 1;
		if(a.data[i]<b.data[i])return -1;
	}
	return 0;
}
hugeint huge_add(hugeint a,hugeint b) {
	hugeint rslt;
	rslt.len = max(a.len,b.len);
	memset(rslt.data,0,110*4);
	for (int i = 0; i < rslt.len; i++) {
		rslt.data[i]=a.data[i]+b.data[i];
	}
	for (int i = 0; i < rslt.len; i++) {
		int t = rslt.data[i];
		if (t > 9) {
			rslt.data[i + 1] += t / 10;
			rslt.data[i] = t % 10;
		}
	}
	for (int i = rslt.len-1; i >= 0; i--) {
		if (rslt.data[i] > 0)break;
		else rslt.len--;
	}
	return rslt;
}
hugeint huge_sq(hugeint a) {
	hugeint rslt;
	rslt.len = 2 * a.len;
	memset(rslt.data,0,110*4);
	for (int i = 0; i < a.len; i++) {
		for (int j = 0; j < a.len; j++) {
			rslt.data[i + j] += a.data[i] * a.data[j];
		}
	}
	for (int i = 0; i < rslt.len; i++) {
		int t = rslt.data[i];
		if (t > 9) {
			rslt.data[i + 1] += t / 10;
			rslt.data[i] = t % 10;
		}
	}
	for (int i = rslt.len- 1; i >= 0; i--) {
		if (rslt.data[i] > 0)break;
		else rslt.len--;
	}
	return rslt;
}
hugeint huge_div2(hugeint a) {
	for (int i = a.len - 1; i >= 0; i--) {
		a.data[i-1]+=(a.data[i]%2)*10;
		a.data[i] /= 2;
	}
	for (int i = a.len- 1; i >= 0; i--) {
		if (a.data[i] > 0)break;
		else a.len--;
	}
	return a;
}
hugeint huge_mid(hugeint a,hugeint b) {
	hugeint rslt=huge_add(a,b);
	return huge_div2(rslt);
}
int faq()
{
	char N[110];
	hugeint n,ans;
	n.len = 0;
	fin >> N;
	int ilen = strlen(N);
	for (int i = 0; i<ilen; i++) {//10^2
		n.data[ilen - i - 1] = N[i] - '0';
		n.len++;
	}
	hugeint lo,hi=n;
	memset(lo.data,0,110*4);
	lo.len=0;
	hugeint one;
	memset(one.data,0,110*4);
	one.data[0]=1;
	one.len=1;
	hugeint add1;
	memset(add1.data,0,110*4);
	add1=huge_add(lo,one);
	while(huge_cmpr(lo,hi)==-1&&huge_cmpr(add1,hi)==-1) {//lg num
		hugeint mid=huge_mid(lo,hi);//10^2
		hugeint res=huge_sq(mid);//10^4
		if(huge_cmpr(res,n)==0) {//10^2
			lo=mid;
			break;
		} else if(huge_cmpr(res,n)==1) {//10^2
			hi=mid;
		} else {
			lo=mid;
			add1=huge_add(lo,one);//10^2
		}
	}
	for(int i=lo.len-1; i>=0; i--)fout<<lo.data[i];//10^2
	return 0;
}
int f=faq();
int main() {
	return 0;
}