CSP-J 入门级 · CSP 2022 入门级第一轮 第 18 题

(3)

1  #include <iostream>
2  
3  using namespace std;
4  
5  int n,k;
6  
7  int solve1()
8  {
9      int l = 0, r = n;
10     while(l <= r){
11         int mid = (l + r) / 2;
12         if (mid * mid <= n) l = mid + 1;
13         else r = mid - 1;
14     }
15     return l - 1;
16 }
17 
18 double solve2(double x)
19 {
20         if (x == 0) return x;
21         for (int i = 0; i < k; i++)
22             x = (x + n / x) / 2;
23     return x;
24 }
25 
26 int main()
27 {
28     cin >> n >> k;
29     double ans = solve2(solve1());
30     cout << ans << ' ' << (ans * ans == n) << endl;
31     return 0;
32 }

假设 int 为32位有符号整数类型，输入的 n 是不超过47000的自然数、k 是不超过 int 表示范围的自然数，完成下面的判断题和单选题：

判断题

1. 该算法最准确的时间复杂度分析结果为 $O(\log n+k)$。 2. 当输入为 9801 1 时，输出的第一个数为 99。 3. 对于任意输入的 $n$，随着所输入 $k$ 的增大，输出的第二个数会变成 $1$。 4. 该程序有存在缺陷。当输入的 $n$ 过大时，第 $12$ 行的乘法有可能溢出，因此应当将 mid 强制转换为 $64$ 位整数再计算

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

这题是二分找整数根 + 牛顿迭代求浮点根的混合玩法，拿到题先看 solve1 的循环条件 mid*mid<=n，确认它返回的是 floor(sqrt(n))，再代入 solve2 的迭代公式一步步算，别被 k 的大小和溢出陷阱带偏。

最容易错在以为 solve1 返回的是 ceil(sqrt(n)) 或者把返回结果直接当最终答案；其次，看到第 12 行 mid*mid 就断定一定溢出，其实 n≤47000 时 mid 最大也就 216，平方远小于 2^31；还有人会把牛顿迭代当成精确数学运算，认为 k 越大 ans*ans 就一定会变成 1，忽略了浮点误差和 n 不是完全平方数时永远不可能精确等于 n；另外，对题 2 的 9801=99² 没反应，直接套公式算出 99 却怀疑程序有问题，这也是常见误区。

这道题考查的是二分查找求整数平方根和牛顿迭代法求浮点平方根的组合应用，属于 CSP 入门级里典型的‘算法主线 + 细节陷阱’题型。命题人喜欢把两个经典算法串在一起，让学生先判断正确性，再代入具体数据算结果，最后还要考虑边界和溢出问题，考察面很广。

先看代码结构：solve1 用二分法找最大的 mid 使 mid*mid<=n，最终返回 l-1，也就是 floor(sqrt(n))；solve2 用牛顿迭代公式 x=(x+n/x)/2 迭代 k 次，从初始值出发逼近 sqrt(n)。main 里先调 solve1 得到整数根 x0，再调 solve2(x0) 得到浮点近似值 ans，最后输出 ans 和 (ans*ans==n) 这个布尔值。

逐题推演：

1. 时间复杂度：solve1 是标准二分，区间长度 n，每次减半，复杂度 O(log n)；solve2 是固定迭代 k 次，复杂度 O(k)；整体就是 O(log n+k)。命题人这里挖的坑是让学生以为二分部分可能更复杂，或者忽略 k 的影响，但答案很直接，选 A 正确。

2. 输入 9801 1：9801 是 99 的平方，solve1 二分一定能找到 mid=99，因为 99*99<=9801 成立，而 100*100>9801，所以返回 99。solve2 从 99 开始迭代 1 次：(99+9801/99)/2 = (99+99)/2 = 99，输出仍是 99。这里容易错的是学生没注意到 n 是完全平方数时牛顿迭代一次就收敛到精确值，或者以为 k=1 只迭代一次就不够，其实题目设计就是让完全平方数时一次就到位。选 A 正确。

3. **k 增大时 ans*ans 会不会变成 1**：只有当 n 是完全平方数且迭代足够多时，ans 才会精确等于 sqrt(n)，此时 ans*ans==n 为真（输出 1）。如果 n 不是完全平方数，比如 n=2，sqrt(2) 是无理数，浮点表示永远有误差，ans*ans 不可能精确等于 n，输出永远是 0。命题人特意考这个逻辑：不是‘k 越大越接近 1’，而是‘只有特定 n 才可能变成 1’。很多学生看到 k 增大就以为精度无限提高，忽略了浮点误差和 n 的性质，所以选 B 错误。

4. **第 12 行 mid*mid 是否溢出**：题目限定 n≤47000，二分过程中 mid 最大也就是 ceil(sqrt(47000))≈216，216*216=46656，远小于 2^31-1≈2.14×10^9，完全不会溢出。命题人故意把‘mid*mid’拎出来让学生警惕，因为一般二分求平方根时 n 可能很大，但这里数据范围很小，是个‘假溢出’陷阱。选 B 错误。

5. 输入 2 1：solve1 二分找 floor(sqrt(2))=1，返回 1。solve2 迭代 1 次：(1+2/1)/2 = 1.5，输出 1.5。选项里最接近的是 C，选 C。

6. 输入 3 10：solve1 返回 floor(sqrt(3))=1。solve2 从 1 开始迭代 10 次，牛顿法收敛极快，1 次后到 2，2 次后到 1.75，3 次后到 1.73214...，后面几次基本不动。最终 ans≈1.732，选项 B 最接近，选 B。

7. 输入 256 11：256 是 16 的平方，solve1 返回 16。solve2 从 16 开始迭代 11 次，第一次就是 (16+256/16)/2 = (16+16)/2 = 16，之后永远 16，输出 16。因为 n 是完全平方数且初始值就是精确根，迭代不会改变结果，所以选 A 等于 16。

考频与趋势：二分查找在题库里共考过 39 题，覆盖 7 个考试级别（2008-2026），近年热度明显上升，2024 年 9 题、2025 年 7 题、2026 年 5 题，说明命题人越来越喜欢用二分做数值逼近或搜索。二分答案单独考了 6 题，但多和单调性结合；数论基础考了 28 题，其中完全平方数相关题目在 CSP 入门级出现频率较高（9 题）。这道题把二分和牛顿迭代串起来，属于‘算法组合’类题目，未来可能继续考察更多迭代法（如二分三分套牛顿、牛顿套二分）或更大数据范围下的溢出处理。

预测：基于现有数据，CSP 入门级今后大概率还会出类似的‘二分 + 数值迭代’题，或者把牛顿法换成更基础的‘二分逼近’来降低难度；同时会加强数据范围，比如 n 到 10^9 甚至 10^18，迫使考生考虑用 long long 或避免乘法溢出。暂无足够依据预测具体年份和题号，但可以确定的是，这类题目会越来越常见，尤其是考察迭代收敛性和浮点误差的细节。

总之，这题的核心是读懂 solve1 的返回值含义，代入 solve2 的迭代公式，再结合数据范围判断溢出，最后用数学直觉处理完全平方数和非完全平方数的区别。做题时别被‘mid*mid’吓到，也别对 k 增大抱幻想，一步步推才是王道。