记录编号	283846	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]大整数开方	最终得分	100
用户昵称	cwm大佬%%%	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2016-07-15 19:47:23	内存使用	0.29 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;

struct Bign{
	static const int N = 1000,M = 1;
	static const int powm = 10;// powm = pow(10,M);
	int a[N];
	// bool_type;
	bool operator < (const Bign &num) const {
		if(a[0] != num.a[0])return a[0] < num.a[0];
		const int *b = num.a;
		int th = a[0];
		while(a[th] == b[th] && th > 0) th--;
		return a[th] < b[th];
	}
	bool operator > (const Bign &num) const {return num < *this;}
	bool operator <= (const Bign &num) const {return !(num < *this);}
	bool operator >= (const Bign &num) const {return !(num > *this);}
	bool operator != (const Bign &num) const {return num < *this  || num > *this;}
	bool operator == (const Bign &num) const {return !(num != *this);}
	// =_type;
	Bign operator = (int num){
		memset(a,0,sizeof(a));
		while(num){
			a[++a[0]] = num % powm;
			num /= powm;
		}
		return *this;
	}
	Bign (int num = 0){*this = num;}
	// +_type;
	Bign operator + (const Bign &num) const {
		Bign ret = 1;
		const int *b = num.a;
		int *c = ret.a, buf = 0;
		for(int &i = c[0]; i <= max(a[0], b[0]) || buf; i++){
			c[i] = a[i] + b[i] + buf;
			buf = c[i] / powm;
			c[i] %= powm;
		}c[0]--;
		return ret;
	}Bign operator += (const Bign &num) const {return *this + num;}
	
	Bign operator + (const int num) const {
		Bign ret = num;
		return *this + ret;
	}Bign operator += (const int num) const {return *this + num;}
	// -_type;
	Bign operator - (const Bign &num) const {
		if(a < num.a) return num - *this;
		Bign ret = 1;
		const int *b = num.a;
		int *c = ret.a, buf = 0; 
		for(int &i = c[0]; i < a[0] || a[i] + buf; i++){
			c[i] = a[i] + powm - b[i] +	buf;
			buf = c[i] / powm - 1;
			c[i] %= powm;
		}
		while((!c[c[0]])&&c[0]>0)c[0]--;
		return ret;
	}Bign operator -= (const Bign &num) const {return *this - num;}
	
	Bign operator - (const int num) const {
		Bign ret = num;
		return *this - ret;
	}Bign operator -= (const int num) const {return *this - num;}
	// *_type;
	Bign operator * (const Bign &num) const {
		Bign ret;
		const int *b = num.a;
		int *c = ret.a;
		for(int i = 1; i <= b[0]; i++){
			int buf = 0;
			for(int j = 1; j <= a[0] || buf; j++){
				c[i+j-1] += a[j] * b[i] + buf;
				buf = c[i+j-1] / powm;
				c[i+j-1] %= powm;
			}
		}c[0] = a[0] + b[0];
		if(!c[c[0]]) c[0]--;
		return ret;
	}Bign operator *= (const Bign &num) const {return *this * num;}
	
	Bign operator * (const int num) const {
		Bign ret = num;
		return *this * ret;
	}Bign operator *= (const int num) const {return *this * num;}
	// /_type;
	Bign operator / (const int num) const {
		Bign ret = 1;
		int *c = ret.a, buf = 0;
		for(int i = a[0]; i > 0; i--){
			buf = buf * powm + a[i];
			c[i] = buf / num;
			buf %= num;
		}c[0] = a[0];
		for(int &i = c[0]; !c[i]; i--);
//		c[0]++;
		buf = 0;
		for(int i = 1; i <= c[0] || buf; i++){
			c[i] += buf;
			buf = c[i] / powm;
		}
		return ret;
	}Bign operator /= (const int num) const {return *this - num;}
	// sqrt;
	friend Bign sqrt (const Bign&);
	// io;
	void in () {
		*this = 0;
		a[0] = 1;
//		int *a = this -> a;
		char buf;
		bool brea=0;
		for(int &i = a[0]; !brea; i++){
			for(int j = 1; j <= M; j++){
				buf = getchar();
				if(buf < '0' || buf > '9')
					{brea = 1; break;}
				a[i] += (buf - '0') * pow(10, j - 1);
			}
		}a[0]-=2;
		int l=1,r=a[0];
		while(l<r){
			int buf=a[l];
			a[l]=a[r];
			a[r]=buf;
			l++; r--;
		}
	}
	void out () {
		int *a = this -> a;
		for(int i = a[0]; i > 0; i--)
			printf("%d", a[i]);
		if(a[0]==0)putchar('0');
	}
};

Bign sqrt (const Bign &num){
	Bign l = 1, r = num;
	Bign mid, buf;
	while(l < r){
		mid = (r + l) / 2;
		buf = mid * mid;
		if(buf == num) break;
		if(buf >= num) r = mid;
		else l = mid + 1;
	}l=l-1;
	return l;
//	return l * l > num? l-1: l;
}

int main(){
	freopen("hugeint.in","r",stdin);
	freopen("hugeint.out","w",stdout);
	Bign a;
	a.in();
//	a.out();
//	putchar('\n');
	a=sqrt(a);
	a.out();
//	while(1);
	return 0;
}