NYOJ 完全平方數個數：數學公式 O(1) 解法

NYOJ「完全平方數的個數」：給定區間 [A, B] (1 ≤ A ≤ B ≤ 2×10⁹)，求區間內完全平方數個數。本文推導 O(1) 數學公式，避免遍歷。

核心公式

完全平方數為 k²。k² ∈ [A, B] ⇔ k ∈ [⌈√A⌉, ⌊√B⌋]。

個數 = ⌊√B⌋ - ⌈√A⌉ + 1 = ⌊√B⌋ - ⌊√(A-1)⌋。

推導過程

• ≤ B 的完全平方數個數 = ⌊√B⌋（即 1², 2², ..., ⌊√B⌋²）。
• ≤ A-1 的完全平方數個數 = ⌊√(A-1)⌋。
• 相減得 [A, B] 內個數。

代碼實現（C++）

#include <cstdio>
#include <cmath>
using namespace std;

int main() {
    long long A, B;
    while (scanf("%lld%lld", &A, &B) == 2) {
        long long cnt = (long long)sqrt(B) - (long long)sqrt(A - 1);
        printf("%lld\n", cnt);
    }
    return 0;
}

精度處理關鍵

1. double 精度足夠：B ≤ 2×10⁹，√B ≤ 44721，double 52 位尾數精確表示整數至 2⁵³ ≈ 9×10¹⁵，無精度問題。
2. 轉長整型截斷：(long long)sqrt(x) 等價於 floor(sqrt(x))（對非負數）。
3. 避免浮點誤差：極端情況下 sqrt(25) 可能得 4.9999999，截斷為 4。修正：

long long isqrt(long long x) {
    long long r = sqrt((double)x);
    while ((r+1)*(r+1) <= x) ++r;
    while (r*r > x) --r;
    return r;
}
// 使用 isqrt(B) - isqrt(A-1) 絕對安全

邊界測試

總結

本題是數學洞察力的直接考察：區間內平方數個數 = ⌊√B⌋ - ⌊√(A-1)⌋。代碼極短，關鍵在於理解公式推導並處理浮點精度邊界。競賽中直接用 sqrt + 截斷通常能過，嚴謹場景建議用整數二分法實現 isqrt。