NOIP 普及组初赛 · NOIP 2011 普及组初赛试题 第 28 题

完善程序 （大整数开方） 输入一个正整数 $n(1\leq n\leq 10^{100})$，试用二分法计算它的平方根的整数部分。

#include<iostream>
#include<string>
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++)
            [      ①     ] +=a.num[i]*b.num[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)
//计算大整数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<=a

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

大数乘法下标为 i+j-1；字符串转数字需减'0'；二分判定 mid*mid 与 target 大小。

乘法下标易错写成 i+j；字符串转数字忘记减'0'；二分更新区间时 over 判断写反。

考点：大整数乘法｜字符串转数字｜二分查找

程序在做什么

输入字符串转大整数数组，用二分法求平方根整数部分，需完善大数乘、加、比及区间更新逻辑。