记录编号	312703	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]大整数开方	最终得分	100
用户昵称	open the window	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2016-09-27 13:23:55	内存使用	0.29 MiB

#include<cstdio>
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
struct UP
{
	int a[201],len;
};
UP ans,l,r,mid;
string s;
int max(int ax,int by)
{
	return ax>by? ax:by;
}
UP add(UP a,UP b)
{
	UP c; int p;
	for (p=1; p<=200; ++p) c.a[p]=0;
	c.len=200;
	for (p=1; p<=max(a.len,b.len); ++p)
	{
		c.a[p]+=a.a[p]+b.a[p];
		c.a[p+1]+=c.a[p]/10;
		c.a[p]%=10;
	}
	while (c.a[c.len]==0 && c.len>1) c.len--;
	return c;
}
UP half(UP t)
{
	int q;
	for (q=t.len; q>1; --q)
	{
		t.a[q-1]+=(t.a[q]%2)*10;
		t.a[q]/=2;
	}
	t.a[1]/=2;
	while (t.a[t.len]==0 && t.len>1) t.len--;
	return t;
}
UP square(UP x)
{
	UP y; int w,v;
	for (w=1; w<=200; ++w) y.a[w]=0;
	y.len=2*x.len;
	for (w=1; w<=x.len; ++w)
	 for (v=1; v<=x.len; ++v)
	  y.a[w+v-1]+=x.a[w]*x.a[v];
	for (w=1; w<2*x.len; ++w)
	{
        y.a[w+1]+=y.a[w]/10;
		y.a[w]%=10;
	}
	while (y.a[y.len]==0 && y.len>1) y.len--;
	return y;
}
int pop(UP e,UP f)
{
	if (e.len>f.len) return 1;
	if (e.len<f.len) return -1;
	for (int u=e.len; u>=1; --u)
	{
		if (e.a[u]==f.a[u]) continue;
		if (e.a[u]>f.a[u]) return 1;
		 else return -1;
	}
	return 0;
}
int main()
{
	 freopen("hugeint.in","r",stdin);
	 freopen("hugeint.out","w",stdout);
     cin>>s;
	 int i;
     for (i=0; i<s.size(); ++i) ans.a[s.size()-i]=s[i]-'0';
	 ans.len=s.size();
     l.a[1]=1; l.len=1; r=ans;
	 while (pop(l,r)<0)
	 {
          mid=half(add(l,r));
		  if (pop(square(mid),ans)>0) r=mid;
		   else l=mid;
		  UP e=l;
		  e.a[1]++;
		  int top=1;
		  while (e.a[top]>10)
		  {
			  e.a[top+1]+=e.a[top]/10;
			  e.a[top]%=10;
			  top++;
		  }
		  if (pop(square(e),ans)>0) break;
	 }
	 for (i=l.len; i>=1; --i) printf("%d",l.a[i]);
     printf("\n");
	 return 0;
}