比赛 |
防止浮躁的小练习v0.8 |
评测结果 |
AAAAAAAAAA |
题目名称 |
大整数开方 |
最终得分 |
100 |
用户昵称 |
Mealy |
运行时间 |
0.157 s |
代码语言 |
C++ |
内存使用 |
0.25 MiB |
提交时间 |
2016-10-31 09:01:05 |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
const int nmax=286;
char ch[nmax];
class poi
{
public:
int s[nmax];
void PreDo()
{
memset(s,0,sizeof(s));
}
void Carry()
{
for(int i=0;i<nmax;i++)
{
s[i+1]+=s[i]/10;
s[i]%=10;
}
}
poi operator + (const poi y) const
{
poi ans;
ans.PreDo();
for(int i=0;i<nmax;i++)
{
ans.s[i]=s[i]+y.s[i];
}
ans.Carry();
return ans;
}
poi operator * (const poi y) const
{
poi ans;
ans.PreDo();
for(int i=0;i<nmax/2;i++)
{
for(int j=0;j<nmax/2;j++)
{
ans.s[i+j]+=s[i]*y.s[j];
}
}
ans.Carry();
return ans;
}
poi operator / (const int y) const
{
poi ans;
ans.PreDo();
for(int i=nmax-1;i>=0;i--)
{
ans.s[i]+=s[i];
ans.s[i-1]+=(ans.s[i]%y)*10;
ans.s[i]=ans.s[i]/y;
}
ans.Carry();
return ans;
}
poi Dec1()
{
for(int i=0;i<nmax;i++)
{
if(!s[i])
{
s[i]=9;
}
else
{
s[i]--;
break;
}
}
Carry();
}
bool operator < (const poi y) const
{
for(int i=nmax-1;i>=0;i--)
{
if(s[i]>y.s[i])
{
return 0;
}
if(s[i]<y.s[i])
{
return 1;
}
}
return 0;
}
bool operator > (const poi y) const
{
for(int i=nmax-1;i>=0;i--)
{
if(s[i]<y.s[i])
{
return 0;
}
if(s[i]>y.s[i])
{
return 1;
}
}
return 0;
}
void Read()
{
scanf("%s",ch);
int len=strlen(ch);
for(int i=0;i<len;i++)
{
s[len-i-1]=ch[i]-'0';
}
}
void Out()
{
int n=nmax-1;
while(!s[n])
{
n--;
}
for(int i=n;i>=0;i--)
{
printf("%d",s[i]);
}
printf("\n");
}
}FJ;
bool Check(poi tmp)
{
tmp=tmp*tmp;
if(tmp>FJ)
{
return 1;
}
else
{
return 0;
}
}
void BiSearch()
{
poi lft;
lft.PreDo();
poi rgt;
rgt.PreDo();
rgt.s[100]=1;
poi mid;
mid.PreDo();
while(lft<rgt)
{
mid=lft+rgt;
mid=mid/2;
if(Check(mid))
{
rgt=mid;
}
else
{
lft=mid;
lft.s[0]++;
lft.Carry();
}
}
if(Check(rgt))
{
lft.Dec1();
lft.Out();
}
else
{
rgt.Dec1();
rgt.Out();
}
}
int main()
{
freopen("hugeint.in","r",stdin);
freopen("hugeint.out","w",stdout);
FJ.PreDo();
FJ.Read();
BiSearch();
return 0;
}