记录编号	334369	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]大整数开方	最终得分	100
用户昵称	GROWL GOOD BOYส็	是否通过	通过
代码语言	C++	运行时间	0.285 s
提交时间	2016-10-31 21:33:47	内存使用	0.29 MiB

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

const int maxn=400+10;

char s1[maxn];

struct Big
{
   int data[maxn],len;
   void init(int x)
   {
      memset(data,0,sizeof data);
      len=1;
      data[len]=x;     
   }
}A,B;
  bool operator > (const Big &a,const  Big &b)
   {
       if(a.len!=b.len)return a.len>b.len;
       for(int i=a.len;i;i--)
       {
          if(a.data[i]!=b.data[i])return a.data[i]>b.data[i];
       }
       return 1;
   }
    bool operator == (const Big &a,const  Big &b)
   {
       if(a.len!=b.len)return 0;
       for(int i=a.len;i;i--)
       {
          if(a.data[i]!=b.data[i])return 0;
       }
       return 1;
   }
   Big operator +(const Big &a,const Big &b)
   {
       Big c;
       c.init(0);
       c.len=max(a.len,b.len);
       for(int i=1;i<=c.len;i++)
       {
           c.data[i]+=a.data[i]+b.data[i];
           if(c.data[i]>=10)
           {
             c.data[i]-=10;
             c.data[i+1]++;
           }
       }  
       if(c.data[c.len+1])c.len++;
       return c;
   }
   Big operator - (const Big &a,const Big &b )
   {
       Big c;
       c.init(0);
       c.len=a.len;
       for(int i=1;i<=c.len;i++)
       {
         c.data[i]+=a.data[i]-b.data[i];
         if(c.data[i]<0)c.data[i]+=10,c.data[i+1]--;
       }
       while(!c.data[c.len]&&c.len>0)c.len--;
       return c;
   }
   Big operator * (const Big &a,const Big &b)
   {
       Big c;
       c.init(0);
       for(int i=1;i<=a.len;i++)
       {
           for(int j=1;j<=b.len;j++)
           {
             c.data[i+j-1]+=a.data[i]*b.data[j];
             c.data[i+j]+=c.data[i+j-1]/10;
             c.data[i+j-1]%=10;
           }    
       }
       c.len=a.len+b.len-1;
       while(c.data[c.len+1])
       {
         c.len++;
         c.data[c.len+1]+=c.data[c.len+1]/10;
         c.data[c.len]%=10;
       }
      while(!c.data[c.len]&&c.len>0)c.len--;
      return c;
   }
   
   void updata(Big &d,int k)
   {
        for(int i=d.len+1;i>=2;i--)
        {
          d.data[i]=d.data[i-1];      
        }
        d.len++;
        d.data[1]=k;
        while(!d.data[d.len]&&d.len>1)d.len--;
   }
   
   Big operator / (const Big &a,const Big &b)
   {
       Big c,d;
       c.init(0),d.init(0);
       for(int i=1;i<=b.len;i++)
       d.data[i]=a.data[i+a.len-b.len];
       d.len=b.len;
       for(int i=a.len;i>=b.len;i--)
       {
               while(d>b)
               {
                c.data[i-b.len+1]++;
                d=d-b;
               }
               if(i>b.len)updata(d,a.data[i-b.len]);
       }
       c.len=a.len-b.len+1;
       while(!c.data[c.len]&&c.len>1)c.len--;
      return c;
   }
   
void Bigprint(Big x)
{
     for(int i=x.len;i>=1;i--)
     {
       printf("%d",x.data[i]);
     }
     if(!x.len)printf("0");
}
int main()
{
    freopen("hugeint.in","r",stdin);
    freopen("hugeint.out","w",stdout);
    scanf("%s",s1+1);
    int len1=strlen(s1+1);
    for(int i=1;i<=len1;i++)
    A.data[i]=s1[len1-i+1]-'0'; 
    A.len=len1;
    Big l=B,r=A;
    l.init(1);
    Big two,one;
    one.init(1);
    two.init(2);
    while(r>l)
    {
        Big mid=(l+r)/two;
        if(mid*mid>A)r=mid-one;
        else l=mid+one;
    };
    if(!(l*l==A))l=l-one;
    Bigprint(l);
    fclose(stdin);
    fclose(stdout);
    return 0;
}