Hiểu bài toán

Bài toán yêu cầu đếm số lượng số chính phương (số là bình phương của một số nguyên không âm) nằm trong khoảng từ 1 đến n (bao gồm n). Với t test case, mỗi test cho một số nguyên n (1 ≤ n ≤ 10^18), ta cần in ra số lượng số chính phương không vượt quá n. Ví dụ, với n = 4, các số chính phương là 1 (1^2) và 4 (2^2), vậy kết quả là 2.

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

Cách Sử dụng hàm sqrt

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        ll n;
        cin >> n;
        cout << (ll)sqrt(n) << '\n';
    }
    return 0;
}

• Time Complexity: O(1) mỗi test case
• Space Complexity: O(1)

Số lượng số chính phương không vượt quá n chính là phần nguyên của căn bậc hai của n, tức ⌊√n⌋. Ví dụ: √4 = 2, √8 ≈ 2.828 -> 2. Ta có thể dùng hàm sqrt để tính giá trị này. Tuy nhiên, do n có thể lên tới 10^18, cần dùng kiểu dữ liệu unsigned long long và cẩn thận với lỗi làm tròn khi chuyển đổi từ double sang integer. Trong hầu hết trường hợp, (ll)sqrt(n) hoạt động tốt, nhưng để chắc chắn, một số coder kiểm tra thêm các giá trị lân cận.

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

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        ull n;
        cin >> n;
        ull lo = 0, hi = 1e9+7; // 1e9+7 vuot qua can bac 2 cua 10^18
        while(lo < hi) {
            ull mid = (lo + hi + 1) / 2;
            if(mid * mid <= n) lo = mid;
            else hi = mid - 1;
        }
        cout << lo << '\n';
    }
    return 0;
}

• Time Complexity: O(log(10^9)) ~ 30 thao tác mỗi test case
• Space Complexity: O(1)

Thay vì dùng hàm sqrt, ta có thể tìm số k lớn nhất sao cho k^2 ≤ n bằng tìm kiếm nhị phân. Ta tìm kiếm k trong khoảng [0, 10^9] (vì √(10^18) = 10^9). Với mỗi mid, ta kiểm tra mid * mid ≤ n. Phương pháp này đảm bảo chính xác tuyệt đối và tránh được vấn đề lỗi số thực.

Cách Kiểm tra chỉnh sửa lỗi số thực

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using u128 = __uint128_t;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        ull n;
        cin >> n;
        ull r = (ull)floor(sqrtl((long double)n));
        while ((u128)(r+1) * (u128)(r+1) <= n) ++r;
        while ((u128)r * (u128)r > n) --r;
        cout << r << '\n';
    }
    return 0;
}

• Time Complexity: O(1) - O(10) (vòng lặp sửa lỗi rất nhanh)
• Space Complexity: O(1)

Để đảm bảo độ chính xác cao nhất khi dùng số thực, ta lấy giá trị khởi đầu từ sqrtl (dạng long double). Sau đó, ta điều chỉnh giá trị này lên hoặc xuống 1 đơn vị cho đến khi tìm ra giá trị đúng nhất. Sử dụng _uint128t để tránh tràn số khi bình phương các số lớn (vì 10^18 * 10^18 lớn hơn giới hạn của unsigned long long).

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

Bài học kinh nghiệm

• Số lượng số chính phương ≤ n là phần nguyên của căn bậc hai của n.
• Với n ≤ 10^18, căn bậc hai của n nằm trong khoảng 10^9, có thể lưu vào kiểu unsigned long long.
• Hàm sqrt có thể gây lỗi làm tròn với số lớn, cần kiểm tra lại hoặc dùng tìm kiếm nhị phân để đảm bảo chính xác.

Lỗi thường gặp

• Sử dụng kiểu int hoặc long long (có dấu) có thể gây lỗi tràn số khi bình phương hoặc xử lý số lớn.
• Quên kiểm tra trường hợp biên (ví dụ: n là số chính phương hoàn hảo) dẫn đến sai kết quả.
• Dùng sqrt(n) cho số lớn mà không kiểm tra lỗi làm tròn (ví dụ: sqrt(10^18) có thể trả về 999999999.999... và khi cast về int sẽ thành 999999999 thay vì 1000000000).