NOIP2011提高组初赛 C++组 完善程序第一题 大整数开方

NOIP2011提高组初赛 C++组  完善程序第一题  大整数开方

输入一个正整数n（1<= n <10^100），试用二分法计算它的平方根的整数部分。

这是我补全的代码，已经运行通过：

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

const int SIZE=200;

struct hugeint
{
    int len,num[SIZE];
};

hugeint times(hugeint a,hugeint b)
{
    int i,j;
    hugeint ans;
    memset(ans.num,0,sizeof(ans.num));
    for (i=1;i<=a.len;i++)
        for (j=1;j<=b.len;j++)
            ans.num[i+j-1]+=a.num[i]*b.num[j];
    for (i=1;i<=a.len+b.len;i++)
    {
        ans.num[i+1]+=ans.num[i]/10;
        ans.num[i]=ans.num[i]%10;
    }
    if (ans.num[a.len+b.len]>0)
        ans.len=a.len+b.len;
    else
        ans.len=a.len+b.len-1;
    return ans;
}

hugeint add(hugeint a,hugeint b)
{
    int i;
    hugeint ans;
    memset(ans.num,0,sizeof(ans.num));
    if (a.len>b.len)
        ans.len=a.len;
    else
        ans.len=b.len;
    for (i=1;i<=ans.len;i++)
    {
        ans.num[i]+=(a.num[i]+b.num[i]);
        ans.num[i+1]+=ans.num[i]/10;
        ans.num[i]%=10;
    }
    if (ans.num[ans.len+1]>0)
        ans.len++;
    return ans;
}

hugeint average(hugeint a,hugeint b)
{
    int i;
    hugeint ans;
    ans=add(a,b);
    for (i=ans.len;i>=2;i--)
    {
        ans.num[i-1]+=(ans.num[i]%2)*10;
        ans.num[i]/=2;
    }
    ans.num[i]/=2;
    if (ans.num[ans.len]==0)
        ans.len--;
    return ans;
}

hugeint plustwo(hugeint a)
{
    int i;
    hugeint ans;
   
    ans=a;
    ans.num[1]+=2;
    i=1;
    while ((i<=ans.len) && (ans.num[i]>=10) )
    {
        ans.num[i+1]+=ans.num[i]/10;
        ans.num[i]%=10;
        i++;
    }
    if (ans.num[ans.len+1]>0)
        ans.len++;
    return ans;
}

bool over(hugeint a,hugeint b)
{
    int i;
    if (a.len<b.len)
        return false;
    if (a.len>b.len)
        return true;
    for (i=a.len;i>=1;i--)
    {
        if (a.num[i]<b.num[i])
            return false;
        if (a.num[i]>b.num[i])
            return true;
    }
    return false;
}

int main()
{
    freopen("highsquare.in","r",stdin);
    freopen("highsquare.out","w",stdout);
    string s;
    int i;
    hugeint target,left,middle,right;
   
    cin>>s;
    memset(target.num,0,sizeof(target.num));
    target.len=s.length();
    for (i=1;i<=target.len;i++)
        target.num[i]=s[target.len-i]-'0';
    memset(left.num,0,sizeof(left.num));
    left.len=1;
    left.num[1]=1;
    right=target;
    do
    {
        middle=average(left,right);
        hugeint sp=times(middle,middle);
        if ( over(sp,target) )
            right=middle;
        else
            left=middle;
    }while (!over(plustwo(left),right));
   
    for (i=left.len;i>=1;i--)
        cout<<left.num[i];
    cout<<endl;
    return 0;
}