c++中如何判断一个数是否为完全平方数_c++数学算法实现【详解】

用sqrt判断需防浮点误差，推荐先转double取整再验证root²和(root+1)²；更稳妥用llround；或采用二分查找，以mid

用 sqrt 判断是否为完全平方数，但要注意浮点误差

直接调用 sqrt 然后取整再平方验证，是最直观的做法，但 double 类型在大整数（比如超过 2^53）时无法精确表示所有整数，会导致误判。

实操建议：

• 对 long long 类型输入，先转成 double 调用 std::sqrt，再向下取整得 root
• 计算 root * root 和 (root + 1) * (root + 1)，检查原数是否等于其中之一
• 更稳妥的做法是用 std::llround(std::sqrt(x)) 后再验证，但需确保 x >= 0

bool isPerfectSquare(long long x) {
    if (x < 0) return false;
    long long r = std::llround(std::sqrt(static_cast(x)));
    return r >= 0 && r * r == x;
}

不用浮点运算：二分查找法判断完全平方数

适用于不允许浮点、或需要 100% 整数精度的场景（如竞赛、嵌入式、大数处理）。时间复杂度 O(log n)，无精度风险。

关键点：

• 搜索范围是 [0, x]，但可优化为 [0, min(x, 1LL （因为 sqrt(2^64) 最大是 2^32）
• 注意 mid * mid 可能溢出，应改用 mid 做条件判断（当 mid > 0）
• 边界情况：x == 0 或 x == 1 必须覆盖

bool isPerfectSquare(long long x) {
    if (x < 0) return false;
    if (x <= 1) return true;
    long long left = 1, right = x / 2; // sqrt(x) <= x/2 for x >= 4
    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if (mid == x / mid && x % mid == 0) return true;
        if (mid < x / mid) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

位运算 + 牛顿迭代：高效且适合高频调用

牛顿迭代收敛极快（通常 5~6 步内收敛到整数根），配合初始值优化（如用 bit length 快速估算），比二分更快，也避免浮点误差——只要全程用整数除法。

注意事项：

• 迭代公式为 next = (cur + x / cur) / 2，必须用整数除法，且要防止 cur == 0
• 初始值选 1 可大幅减少迭代次数
• 必须在迭代前后检查 cur * cur == x，因为整数牛顿法可能上下震荡，不保证最后一次恰好命中

bool isPerfectSquare(long long x) {
    if (x < 0) return false;
    if (x <= 1) return true;
    long long r = x;
    while (r > x / r) r = (r + x / r) / 2; // integer Newton
    return r * r == x || (r + 1) * (r + 1) == x || (r - 1) * (r - 1) == x;
}

负数、零、大整数的边界行为必须显式处理

sqrt 对负数返回 NaN，而整数运算中负数永远不是完全平方数；0 和 1 是合法完全平方数；LLONG_MAX 这类值传给 sqrt 会丢失精度，必须靠整数方法兜底。

常见翻车点：

• 忘记检查 x ，导致 sqrt 返回 NaN，后续比较失效
• 用 (int)sqrt(x) 截断而非四舍五入或向下取整，对 25, 36 等没问题，但对 999999999999999999 就错
• 二分时写 mid = (left + right) / 2 导致 left + right 溢出（尤其 long long）
• 牛顿迭代未设终止条件，遇到某些值（如 x == 2）可能死循环

真正稳定的做法，是把整数二分作为 fallback，只在确认输入范围安全时才用 sqrt 加速。精度和边界，从来不是“理论上没问题”就能绕开的。