CSP-J 2022 第一轮 第 31 题：程序（三）：mid mid是否存在溢出风险

题目

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 表示范围的自然数，完成下面的判断题和单选题：

该程序有存在缺陷。当输入的 $n$ 过大时，第 $12$ 行的乘法有可能溢出，因此应当将 mid 强制转换为 $64$ 位整数再计算。

选项

• A. 正确
• B. 错误

答案

B

题解

选 B．错误。在题目给定的范围内，mid * mid 不会溢出。

32 位有符号整数的最大值为 \(2^{31}-1=2147483647\)。关键在于：r 可以达到 47000，但 mid 不会达到这么大。

• 当 \(0\le n\le5\) 时，mid 最大不超过 5，显然不会溢出。
• 当 \(6\le n\le47000\) 时，第一次循环中

\[ mid=\lfloor n/2\rfloor\le23500, \] 因而 \[ mid^2\le23500^2=552250000<2147483647. \] 同时，这时 \(mid^2>n\)，所以执行 r = mid - 1。此后 r 只会减小或保持不变，后续循环的 mid 都不超过 23499，乘法也不会溢出。

因此，不能仅凭 \(47000^2\) 超过 int 上限就判定溢出，还要看 mid 实际能取到的值。