（NOIP2011）大整数开方

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

#include<iostream>
#include<string>
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++)
            ①;
    for(i=1;i<=a.len+b.len;i++) {
        ans.num[i+1]+=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+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]+=(④)*10;
        ans.num[i]/=2;
    }
    ans.num[1]/=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)⑤;
    return ans;
}

bool over(hugeint a,hugeint b) {
    int i;
    if(⑥)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]-⑦;
    memset(left.num,0,sizeof(left.num));
    left.len=1;
    left.num[1]=1;
    right=target;
    do{
        middle=average(left,right);
        if(over(⑧)) 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;
}

①处应填（ ）。
{{ select(1) }}

• ans.num[j-i+1]
• ans.num[i+j-1]
• ans.num[i+j+1]
• ans.num[i-j+1]

②处应填（ ）。
{{ select(2) }}

• ans.num[i]=ans.num[i-1]%10
• ans.num[i]=ans.num[i]/10
• ans.num[i]=ans.num[i]%10
• ans.num[i]=ans.num[i-1]*10

③处应填（ ）。
{{ select(3) }}

• ans.num[i]+a.num[i]+b.num[i]
• ans.num[i]=abs(a.num[i]-b.num[i])
• ans.num[i]=min(a.num[i],b.num[i])
• ans.num[i]=a.num[i]+b.num[i]

④处应填（ ）。
{{ select(4) }}

• ans.num[i]%1
• ans.num[i]&2
• ans.num[i-1]&1
• ans.num[i]%2

⑤处应填（ ）。
{{ select(5) }}

• ans.num[ans.len+1]%10
• ans.len++
• ans.len--
• ans.num[ans.len++]=1

⑥处应填（ ）。
{{ select(6) }}

• times(a,a)<times(a,b)
• a.len<=b.len
• a.len<b.len
• add(a,a)<add(b,b)

⑦处应填（ ）。
{{ select(7) }}

• 65
• 97
• 34
• 48

⑧处应填（ ）。
{{ select(8) }}

• times(left,right),target
• times(middle+1,middle+1),target
• times(middle,middle),target
• add(middle,middle),target