1. Tóm tắt đề bài

Cho hai số nguyên dương ~a~ và ~b~ (~a \le b~). Hãy đếm xem có bao nhiêu số chính phương nằm trong đoạn ~[a, b]~.

• Dữ liệu vào (Input):
  • Gồm một dòng chứa hai số nguyên dương ~a, b~ cách nhau một khoảng trắng (~1 \le a \le b \le 10^9~).
• Dữ liệu ra (Output):
  • Một số nguyên duy nhất là số lượng số chính phương tìm được.

2. Phân tích bài toán & Giới hạn

• Giới hạn bài toán:

  • ~1 \le a \le b \le 10^9~.
  • Vì ~b~ có thể lên tới ~10^9~, nếu dùng vòng lặp duyệt từng số ~i~ từ ~a~ đến ~b~ rồi kiểm tra xem ~i~ có phải là số chính phương hay không, số bước lặp có thể lên tới ~10^9~ phép tính ~\rightarrow~ Bị lỗi quá thời gian (Time Limit Exceeded - TLE).

• Ý tưởng toán học tối ưu:

  • Một số ~x~ là số chính phương khi và chỉ khi tồn tại số nguyên dương ~k~ sao cho ~x = k^2~.
  • Số chính phương ~x~ nằm trong đoạn ~[a, b]~ nghĩa là: ~a \le k^2 \le b \iff \sqrt{a} \le k \le \sqrt{b}~
  • Do ~k~ là số nguyên dương:
    • Giá trị nhỏ nhất của ~k~ là số nguyên đầu tiên lớn hơn hoặc bằng ~\sqrt{a}~, tức là: ~k_{\min} = \lceil \sqrt{a} \rceil~ Trong lập trình C++, ta tính bằng: ceil(sqrt(a)).
    • Giá trị lớn nhất của ~k~ là số nguyên lớn nhất nhỏ hơn hoặc bằng ~\sqrt{b}~, tức là: ~k_{\max} = \lfloor \sqrt{b} \rfloor~ Trong lập trình C++, khi gán căn bậc hai vào biến kiểu nguyên, phần thập phân tự động bị cắt bỏ, tức là: floor(sqrt(b)) hay viết gọn là sqrt(b).
  • Khi đó, số lượng số chính phương trong đoạn ~[a, b]~ chính là số lượng số nguyên ~k~ thỏa mãn ~k_{\min} \le k \le k_{\max}~:
    • Nếu ~k_{\min} \le k_{\max}~: Số lượng số là ~k_{\max} - k_{\min} + 1~.
    • Nếu ~k_{\min} > k_{\max}~: Không có số chính phương nào trong đoạn, kết quả là ~0~.

• Kiểu dữ liệu:

  • ~a, b \le 10^9~, các giá trị căn bậc hai tối đa ~\sqrt{10^9} \approx 31622~. Dùng kiểu dữ liệu long long để tránh rủi ro tràn số khi làm việc với phép nhân hoặc ép kiểu số thực.

3. Thuật toán xử lý

• Các bước thực hiện:

  1. Khai báo hai biến a và b kiểu long long.
  2. Đọc dữ liệu chuẩn: cin >> a >> b;.
  3. Tính cận dưới ~k_{\min}~ và cận trên ~k_{\max}~:
     • long long can_duoi = ceil(sqrt(a));
     • long long can_tren = sqrt(b);
  4. Tính kết quả:
     • Khởi tạo biến đếm so_luong = 0;.
     • Nếu can_duoi <= can_tren:
       • so_luong = can_tren - can_duoi + 1;
  5. In so_luong ra màn hình và xuống dòng bằng cout << endl;.

• Độ phức tạp:

  • Thời gian: ~\mathcal{O}(1)~ — Chỉ dùng vài phép toán căn bậc hai và phép trừ, máy tính xử lý tức thì trong thời gian ~< 0.001~ giây.
  • Không gian (bộ nhớ): ~\mathcal{O}(1)~ — Chỉ dùng các biến đơn lẻ.

4. Mã nguồn cài đặt (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Tối ưu tốc độ nhập/xuất chuẩn
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long a, b;
    cin >> a >> b;

    // can_duoi là số nguyên nhỏ nhất sao cho can_duoi * can_duoi >= a
    long long can_duoi = ceil(sqrt(a));

    // can_tren là số nguyên lớn nhất sao cho can_tren * can_tren <= b
    long long can_tren = sqrt(b);

    long long so_luong = 0;
    if (can_duoi <= can_tren) {
        so_luong = can_tren - can_duoi + 1;
    }

    cout << so_luong << endl;

    return 0;
}