记录编号	261826	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]大整数开方	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-05-18 17:56:42	内存使用	0.09 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define copy(a,b) memcpy(a,b,sizeof(int)*maxn)
using namespace std;
const int maxn=310,ONE[maxn]={1,1,0};
void input(int*);
void output(const int*);
int cmp(const int*,const int*);
void plus(const int*,const int*,int*);
void subt(const int*,const int*,int*);
void multi(const int*,const int*,int*);
void divide2(const int*,int*,bool=false);
int MAIN();
char s[maxn];
int a[maxn],d[maxn],n[maxn],c[maxn],b[maxn],r,rr=MAIN();
int main(){;}
inline int MAIN(){
#define MINE
#ifdef MINE
	freopen("hugeint.in","r",stdin);
	freopen("hugeint.out","w",stdout);
#endif
	input(n);
	divide2(n,a);
	divide2(a,d,true);
	for(;;){
		multi(a,a,b);
		r=cmp(b,n);
		plus(a,ONE,c);
		multi(c,c,b);
		rr=cmp(b,n);
		if(!r||(r<0&&rr>0))break;
		if(r<0)plus(a,d,b);
		else if(r>0)subt(a,d,b);
		copy(a,b);
		divide2(d,b,true);
		copy(d,b);
	}
	output(a);
	return 0;
}
inline void input(int* a){
	memset(a,0,sizeof(int)*maxn);
	scanf("%s",s);
	a[0]=strlen(s);
	for(int i=0;i<a[0];i++)a[a[0]-i]=s[i]-'0';
}
inline void output(const int* a){
	if(!a[0])putchar('0');
	else for(int i=a[0];i;i--)printf("%d",a[i]);
}
inline int cmp(const int* a,const int* b){
	if(a[0]!=b[0])return a[0]-b[0];
	for(int i=a[0];i;i--)if(a[i]!=b[i])return a[i]-b[i];
	return 0;
}
inline void plus(const int* a,const int* b,int* c){
	memset(c,0,sizeof(int)*maxn);
	c[0]=max(a[0],b[0]);
	for(int i=1;i<=c[0];i++){
		c[i]+=a[i]+b[i];
		c[i+1]+=c[i]/10;
		c[i]%=10;
	}
	if(c[c[0]+1])c[0]++;
}
inline void subt(const int* a,const int* b,int* c){
	memset(c,0,sizeof(int)*maxn);
	c[0]=max(a[0],b[0]);
	for(int i=1;i<=c[0];i++){
		c[i]+=a[i]-b[i];
		if(c[i]<0){
			c[i+1]--;
			c[i]+=10;
		}
	}
	if(!c[c[0]])c[0]--;
}
inline void multi(const int* a,const int* b,int* c){
	memset(c,0,sizeof(int)*maxn);
	if(!a[0]||!b[0])return;
	c[0]=a[0]+b[0];
	for(int i=1;i<=a[0];i++)for(int j=1;j<=b[0];j++){
		c[i+j-1]+=a[i]*b[j];
		c[i+j]+=c[i+j-1]/10;
		c[i+j-1]%=10;
	}
	if(!c[c[0]])c[0]--;
}
inline void divide2(const int* a,int* c,bool b){//向上取整
	memset(c,0,sizeof(int)*maxn);
	if(b&&a[1]&1)plus(a,ONE,c);
	else copy(c,a);
	for(int i=c[0];i;i--){
		if(i>1&&(c[i]&1))c[i-1]+=10;
		c[i]>>=1;
	}
	if(!c[c[0]])c[0]--;
}