比赛 防止颓废的小练习v0.2 评测结果 AAAAAAAAAA
题目名称 大整数开方 最终得分 100
用户昵称 L_in 运行时间 0.025 s
代码语言 C++ 内存使用 0.32 MiB
提交时间 2016-10-18 19:13:24
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct BigNum{
	int a[110],len;
	BigNum(){len=1;memset(a,0,sizeof(a));}
	void input(string s){
		len=s.size();
		for(int i=0;i<len;i++)a[len-i]=s[i]-'0';
	}
	BigNum operator+(const BigNum&x)const{
		BigNum c;
		c.len=max(len,x.len);
		for(int i=1;i<=c.len;i++){
			c.a[i]+=a[i]+x.a[i];
			c.a[i+1]+=c.a[i]/10;
			c.a[i]%=10;
		}
		if(c.a[c.len+1])c.len++;
		return c;
	}
	BigNum operator-(const BigNum&x)const{
		BigNum c;
		c.len=max(len,x.len);
		for(int i=1;i<=c.len;i++){
			c.a[i]+=a[i]-x.a[i];
			if(c.a[i]<0)c.a[i+1]-=1,c.a[i]+=10;
		}
		while(c.len>1&&!c.a[c.len])c.len--;
		return c;
	}
	BigNum operator*(const BigNum&x)const{
		BigNum c;
		c.len=len+x.len-1;
		for(int i=1;i<=len;i++){
			for(int j=1;j<=len;j++){
				c.a[i+j-1]+=a[i]*x.a[j];
				c.a[i+j]+=c.a[i+j-1]/10;
				c.a[i+j-1]%=10;
			}
		}
		if(c.a[c.len+1])c.len++;
		return c;
	}
	BigNum operator/(int x)const{
		BigNum c;
		c.len=len;
		int now=0;
		for(int i=len;i>=1;i--){
			now=now*10+a[i];
			c.a[i]=now/x;
			now%=x;
		}
		while(c.len>1&&!c.a[c.len])c.len--;
		return c;
	}
	bool operator<=(const BigNum&x)const{
		if(len<x.len)return true;
		if(len>x.len)return false;
		for(int i=len;i>=1;i--){
			if(a[i]<x.a[i])return true;
			if(a[i]>x.a[i])return false;
		}
		return true;
	}
	void output(){
		for(int i=len;i>=1;i--)printf("%d",a[i]);
		printf("\n");
	}
}L,R,mid,bigint,one;
int main()
{
	freopen("hugeint.in","r",stdin);
	freopen("hugeint.out","w",stdout);
	string s;
	cin>>s;
	bigint.input(s);
	R=bigint;
	L.input("1");
	one.input("1");
	while(L<=R){
		mid=(L+R)/2;
		if(mid*mid<=bigint)L=mid+one;
		else R=mid-one;
	}
	R.output();
	fclose(stdin);fclose(stdout);
	return 0;
}
/* 

*/