C++二分法求平方根遇大数失效问题求助

AI 小北

2026-8-6

问题原因与解决方案

核心问题：整数溢出与数据类型范围不足

你的代码失效有两个关键原因：

输入值超出int类型范围：C++中int通常是4字节，取值范围仅为-2147483648到2147483647。你输入的2000000000000000、-3456735426738都远超出这个范围，读入到int n时会直接发生溢出，导致变量存储错误的截断值。
计算过程中溢出：就算输入的数在int范围内（比如2000000000），执行m*m时也会溢出。比如当m取46341时，46341*46341=2147488281，已经超过int的最大值，溢出后会变成负数，导致m*m <=n的判断逻辑完全混乱。

Python不会出现这个问题是因为它的整数可以自动扩容，没有固定范围限制。

修复后的代码

把所有相关变量换成long long类型，同时增加负数的处理逻辑：

#include <iostream>
using namespace std;

int main() {
    long long n; 
    cin >> n;
    
    // 处理负数情况：实数范围内负数无平方根
    if (n < 0) {
        cout << "负数无实数平方根" << endl;
        return 0;
    }
    
    long long l = 0, r = n + 1;
    while (r - l > 1) {
        long long m = (r + l) / 2;
        // 用除法代替乘法避免溢出：m <= n/m 等价于 m*m <=n（当m>0时）
        if (m <= n / m) { 
            l = m;
        } else {
            r = m;
        }
    }
    cout << l;
    return 0;
}

额外说明：用m <= n/m代替m*m <=n是为了进一步避免long long也可能出现的极端大数溢出（比如当n接近2^63-1时，m*m依然可能溢出），这样的写法更安全。