Hiểu bài toán

Bài toán yêu cầu đếm số lượng số chính phương (squares) nằm trong khoảng từ L đến R (giới hạn bao gồm). Với các ràng buộc L, R có thể lên tới 10^12, cần một giải pháp hiệu quả hơn việc duyệt qua tất cả các số trong khoảng [L, R]. Số chính phương là bình phương của một số tự nhiên (k >= 0).

Các cách tiếp cận

Cách Duyệt bình phương (Math)

#include <stdio.h>
#include <math.h>

int main() {
    long long l, r;
    scanf("%lld %lld", &l, &r);

    // Tìm số nguyên lớn nhất k1 sao cho k1^2 <= r
    long long k1 = (long long)sqrt(r);

    // Tìm số nguyên nhỏ nhất k2 sao cho k2^2 >= l
    long long k2 = (long long)ceil(sqrt(l));

    // Nếu k1 < k2 thì không có số chính phương nào
    if (k1 < k2) {
        printf("0");
    } else {
        printf("%lld", k1 - k2 + 1);
    }

    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Phương pháp này dựa vào việc quan sát rằng số lượng số chính phương trong khoảng [L, R] bằng số lượng số tự nhiên k使得 k^2 nằm trong khoảng đó. Cụ thể, nếu a là số nguyên nhỏ nhất sao cho a^2 >= L và b là số nguyên lớn nhất sao cho b^2 <= R, thì kết quả là b - a + 1. Hàm sqrt() trong C trả về số thực, ta ép kiểu về long long. Cần chú ý cách tính a (dùng ceil) và b (dùng floor). Ví dụ: L=2, R=5. sqrt(5) ~ 2.23 -> b=2. sqrt(2) ~ 1.41 -> ceil là 2. Kết quả là 2-2+1=1.

Cách Brute Force Loop

#include <stdio.h>
#include <math.h>

int main() {
    long long l, r;
    scanf("%lld %lld", &l, &r);
    long long cnt = 0;

    // Vòng lặp chạy từ số nhỏ nhất có thể là căn bậc 2 của L
    // Tới số lớn nhất có thể là căn bậc 2 của R
    // Cần chỉnh sửa biên để đảm bảo an toàn
    for (long long i = sqrt(l); i * i <= r; i++) {
        if (i * i >= l) {
            cnt++;
        }
    }

    printf("%lld", cnt);
    return 0;
}

• Time Complexity: O(sqrt(R))
• Space Complexity: O(1)

Phương pháp này duyệt qua tất cả các số k từ floor(sqrt(L)) đến ceil(sqrt(R)) và kiểm tra xem k^2 có nằm trong [L, R] không. Độ phức tạp phụ thuộc vào giá trị của R, khoảng O(sqrt(R)). Với R=10^12, số lần lặp là 10^6, hoàn toàn chấp nhận được trong thời gian giới hạn của các kỳ thi (thường là 1-2 giây). Các solution mẫu 1 và 3 sử dụng logic này.

Cách Binary Search (Tìm kiếm nhị phân)

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

int main() {
    long long L, R;
    cin >> L >> R;

    // Tìm kiếm nhị phân để tìm số k nhỏ nhất sao cho k*k >= L
    long long low = 0, high = 1e9 + 7; // high足够大
    long long start = 0;
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (mid * mid >= L) {
            start = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    // Tìm kiếm nhị phân để tìm số k lớn nhất sao cho k*k <= R
    low = 0; high = 1e9 + 7;
    long long end = 0;
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (mid * mid <= R) {
            end = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    if (start > end) cout << 0;
    else cout << end - start + 1;

    return 0;
}

• Time Complexity: O(log(R))
• Space Complexity: O(1)

Đây là một cách tiếp cận tổng quát hơn, chia đôi không gian tìm kiếm để tìm ra số k thỏa mãn. Tuy nhiên, với bài toán này, việc dùng hàm sqrt() (số học) hiệu quả và ngắn gọn hơn. Binary search thường được dùng khi giá trị cần tìm quá lớn (ví dụ 10^18) hoặc khi hàm bình phương có thể bị tràn số nếu không cẩn thận, nhưng với 10^12 thì sqrt là đủ.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể biến đổi từ việc đếm số chính phương trong [L, R] sang bài toán tìm số lượng số nguyên k sao cho sqrt(L) <= k <= sqrt(R).
• Sử dụng hàm sqrt() và ceil/floor là cách hiệu quả nhất về thời gian chạy O(1).
• Kiểu dữ liệu long long (64-bit) là bắt buộc vì L, R có thể lên tới 10^12.

Lỗi thường gặp

• Tràn số (Overflow): Nếu dùng biến int (32-bit) để lưu L, R hoặc kết quả bình phương ii, sẽ gây tràn số với R > 210^9.
• Lỗi số thực (Floating point error): Khi tính sqrt(10^12) hoặc các số lớn, hàm sqrt trả về số thực có thể sai một chút ở số lẻ. Ví dụ sqrt(25) có thể trả về 4.9999999 và ép kiểu về long long sẽ thành 4. Cần dùng hàm làm tròn (ceil) hoặc cộng trừ biên.
• Xử lý biên: Các số chính phương nằm ngay ranh giới (L, R) cần được đếm chính xác. Logic sqrt(L) - 1 hoặc ceil cần được kiểm tra kỹ.