大整数开方

出自NOIP2011提高组初赛完善程序第一题

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

#include<bits/stdc++.h>
using namespace std;

const int SIZE=200;
struct hugeint{
    int len,num[SIZE];
};//其中len表示大整数的位数；num[1]表示个位，num[2]表示十位，以此类推

hugeint times(hugeint a,hugeint b)//计算大整数a和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)//计算大整数a和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)//计算大整数a和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[1]/=2;

    if (ans.num[ans.len]==0)
        ans.len--;

    return ans;
}

hugeint plustwo(hugeint a)//计算大整数a加2之后的结果
{
    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)//若大整数a>b则返回true，否则返回false
{
    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( ) {
    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);
        if(over(times(middle,middle),terget))
            right=middle;
        else
            left=middle;
    }while(!over(plustwo(left),right));

    for(i=left.len;i>=1;i--)
        cout<<left.num[i];

    return 0;
}

这道题目主要考察高精度。高精度最需要注意的是进位、借位处理。

加法进位：c[i]=a[i]+b[i];
        if(c[i]>=10){c[i]%=10;++c[i+1];}
减法借位：if(a[i]<b[i]){--a[i+1];a[i]+=10;}
        c[i]=a[i]-b[i];
乘法进位：c[i+j-1]+=a[i]*b[j]+x;
        x=c[i+j-1]/10;
        c[i+j-1]%10;