比赛 |
防止颓废的小练习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;
}
/*
*/