NOIP 提高组初赛 · NOIP 2011 提高组初赛试题 第 27 题

完善程序 （大整数开方） 输入一个正整数 $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<=ans

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

这题核心就是大数模拟，但考的是你懂不懂乘法进位和加法对齐。记住 num[1] 是个位，乘法里 a.num[i]*b.num[j] 的积要落在 ans.num[i+j-1] 上，加法就是同位相加、满十进一。二分求平方根时，mid*mid 去和 target 比大小，比完再调整左右边界，最后输出 left 就行。

最容易栽跟头的是把乘法结果放错位置，写成 ans.num[i+j] 或 ans.num[i]*j，结果数组错一位后面全乱；加法里忘记把进位写回 ans.num[i+1]，只做了取余；判奇偶时把 ans.num[i]%2 写成 ans.num[i]/2；长度维护时漏掉 ans.len++；字符转数字忘了减'0'；二分里比较对象写反，把 middle 和 left 比成 middle 和 target，导致逻辑全崩。

这道题考查大整数运算模拟和二分求平方根，属于信息学竞赛里经典的“手写大数”题型。命题人喜欢挖坑在进位处理和数组下标偏移上，因为学生容易把位权搞反或者忘记更新长度。拿到题先想：大整数结构里 num[1] 是个位，num[2] 是十位，乘法 a*b 的第 i 位和第 j 位相乘，结果应该落在第 i+j-1 位（因为个位乘个位还在个位），加法是同位相加、满十进一，二分开方就是不断取中点、平方、比较、收缩区间。按这个主线推，每个空自然就能填出来。

先看 times 函数。它要算两个大数乘积。外层循环 i 从 1 到 a.len，内层 j 从 1 到 b.len，a.num[i]*b.num[j] 的积要加到 ans.num[i+j-1] 上，所以①填 ans.num[i+j-1]。接下来处理进位：从低位到高位，ans.num[i+1] 加上 ans.num[i]/10 的进位，同时 ans.num[i] 保留个位数，即 ans.num[i]%=10，所以②填 ans.num[i]=ans.num[i]%10。长度判断里，如果最高位非零，长度就是 a.len+b.len，否则减一，这部分逻辑题目已经写好了，不用动。

再看 add 函数。两个大数相加，先对齐长度（取较长的那个），然后从低位到高位逐位加：ans.num[i] 加上 a.num[i] 和 b.num[i]，满十进一到 ans.num[i+1]，当前位取余，所以③填 a.num[i]+b.num[i]。最后如果最高位进位了，长度加一，这部分也已有。

average 函数是求 (a+b)/2 的整数部分，先加，然后从高位到低位不断除以 2 并处理进位。这里有个技巧：高位除以 2 的余数要乘 10 加到下一位，所以④填 ans.num[i]%2（或者 ans.num[i]&1，效果一样）。

plustwo 函数很简单，给大数加 2，从个位开始进位，如果最高位进位了，长度要加一，所以⑤填 ans.len++（或 ans.len=ans.len+1）。

over 函数比较两个大数大小，先看长度，短的一定小，所以⑥填 a.len<b.len。然后逐位比较，从高位到低位，遇到小于直接返回 false，大于返回 true，相等继续，最后返回 false。

main 函数里，先把输入的字符串转成大数 target，字符转数字要减'0'，所以⑦填'0'或 48。二分区间 left 初始为 1，right 为 target。循环里取中点 middle=average(left,right)，然后判断 middle*middle 是否大于 target，如果大就把 right 设为 middle，否则 left 设为 middle。所以⑧填 times(middle,middle),target。循环条件写的是 while(!over(plustwo(left),right))，意思是当 left+2 不大于 right 时继续，这样能保证最后 left 是平方根的整数部分。

输出时直接从 left 的 num 数组倒序打印就行。

易错点再强调一遍：乘法下标 i+j-1 是灵魂，很多人会写成 i+j 导致结果错位一位；加法忘记把进位写回 ans.num[i+1]；average 里把取余写成除法；plustwo 长度没加；字符转数字忘减'0'；二分比较对象写反。这些坑在考场上很容易丢分，一定要仔细。

从考频看，基础算法（大数模拟、二分）在题库里共考过 30 题，覆盖 2007-2025 年全部三个级别。逐年分布：2007 年 2 题、2008 年 1 题、2009 年 4 题、2010 年 4 题、2011 年 5 题、2012 年 1 题、2013 年 1 题、2014 年 2 题、2016 年 1 题、2019 年 1 题、2021 年 4 题、2024 年 2 题、2025 年 2 题。分赛事看，NOIP 提高组初赛 13 题、CSP 提高级 9 题、NOIP 普及组初赛 8 题。这类“手写大数 + 二分/模拟”的题在提高组初赛里出现频率很高，尤其是像 2011 年这种年份，当年就考了 5 题，说明命题人很看重学生的手写能力和对算法流程的掌控。

未来怎么考？从数据看，2021 年又考了 4 题，2024、2025 各 2 题，呈现震荡但总体稳定的趋势。可以预测：提高组初赛大概率还会继续考这类大数模拟或二分求极值的问题，可能是大数除法、大数幂取模、或者更复杂的二分区间收缩。至于具体考哪个大数运算，目前数据不足以支撑精确预测，只能说“暂无足够依据预测”，但方向肯定是围绕手写大数展开。