（大整数开方） 输入一个正整数n（1≤n＜10100），试用二分法计算它的平方根的整数部分。

#include <iostream>
#include <cstring>
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++)
            【第1空】 +=  a.num[i]  * b.num[j];

    for(i = 1; i <= a.len + b.len; i++)
    {
        ans.num[i + 1] += ans.num[i] / 10;
        【第2空】;
    }

    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] += 【第3空】;
        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] += (【第4空】) * 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)
        【第5空】;
    return ans;
}

bool over(hugeint a, hugeint b)
//若大整数 a>b 则返回 true，否则返回 false
{
    int i;

    if(【第6空】)
        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] - 【第7空】;
    memset(left.num, 0, sizeof(left.num));
    left.len = 1;
    left.num[1] = 1;
    right = target;
    do
    {
        middle = average(left, right);
        if(over(【第8空】))
            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;
}

请填写【第4空】。

{{ input(1) }}