Hiểu bài toán

Cho số nguyên không âm K (0 ≤ K ≤ 2 * 10^5). Tìm số bộ ba số nguyên dương (A, B, C) sao cho tích A * B * C ≤ K. Các bộ khác nhau về thứ tự được coi là khác nhau (ví dụ (1, 1, 2), (1, 2, 1), (2, 1, 1) đều tính là 3 bộ riêng biệt).

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

Cách Brute Force lồng nhau

#include <bits/stdc++.h>
using namespace std;
int main() {
    int k;
    cin >> k;
    long long count = 0;
    for (int a = 1; a <= k; a++) {
        for (int b = 1; a * b <= k; b++) {
            count += k / (a * b);
        }
    }
    cout << count;
}

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

Đây là cách tiếp cận trực tiếp nhất. Ta duyệt qua tất cả các giá trị hợp lệ của A và B. Với mỗi cặp (A, B) sao cho AB ≤ K, số lượng giá trị của C thỏa mãn ABC ≤ K là floor(K / (AB)). Ta cộng dồn số lượng này vào biến đếm.

Độ phức tạp:

• Vòng lặp ngoài cùng chạy K lần.
• Với mỗi A, vòng lặp trong chạy K/A lần.
• Tổng số lần lặp là K/1 + K/2 + K/3 + ... + K/K ≈ K * log(K).
• Với K = 210^5, Klog(K) ≈ 210^5 * 12 ≈ 2.410^6, chạy rất nhanh.

Lưu ý: Khi K = 0, vòng lặp for(int a=1; a<=k; a++) sẽ không chạy, biến count mặc định là 0, kết quả đúng là 0 (vì không có bộ số nguyên dương nào có tích bằng 0).

Cách Tối ưu với Biến phân loại

#include <bits/stdc++.h>
using namespace std;
int main() {
    int k;
    cin >> k;
    long long s = 0;
    for (int i = 1; i <= k; ++i) {
        for (int j = 1; j <= k / i; ++j) {
            s += k / (i * j);
        }
    }
    cout << s;
}

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

Đây là biến thể của cách tiếp cận Brute Force, chỉ khác biệt về tên biến và cú pháp.

Cách hoạt động:

• Vòng lặp i (tương đương A) chạy từ 1 đến K.
• Vòng lặp j (tương đương B) chạy từ 1 đến K/i. Điều kiện j <= K/i đảm bảo rằng i*j <= K, loại bỏ các trường hợp không cần thiết.
• k / (i*j) (tương đương k / (A*B)) cho biết số lượng giá trị của C (từ 1 đến k/(A*B)) thỏa mãn.

Đây là giải pháp tối ưu nhất có thể đạt được với K nhỏ (200,000) và là phương pháp chuẩn được chấp nhận trong bài toán này.

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

Bài học kinh nghiệm

• Bài toán có thể biến đổi thành bài toán đếm tổng: Đếm (A, B, C) sao cho ABC ≤ K. Thay vì duyệt C, ta tính số lượng C hợp lệ cho mỗi (A, B) bằng phép chia nguyên: floor(K / (A*B)).
• Vì K nhỏ (≤ 200,000), ta có thể sử dụng thuật toán lồng nhau với độ phức tạp tổng thể O(K log K), hoàn toàn đủ nhanh (khoảng 2.4 triệu phép tính).
• Vòng lặp thứ hai chỉ cần chạy đến K/A thay vì K để tối ưu.

Lỗi thường gặp

• Sai kiểu dữ liệu: Biến đếm kết quả phải là long long (hoặc unsigned long long) vì kết quả có thể lớn hơn 2^31 - 1 (ví dụ K=10^5 cho kết quả khoảng 1.5 * 10^9).
• Xử lý K = 0: Các giải pháp trên dùng số nguyên dương (bắt đầu từ 1) nên khi K=0, vòng lặp không chạy và trả về 0 là đúng. Tuy nhiên, nếu dùng số tự nhiên (unsigned) hoặc logic sai có thể sinh ra lỗi.
• Tràn số khi tính toán: a * b có thể tràn số int nếu tính nhẩm không cẩn thận, nhưng trong điều kiện vòng lặp a*b <= k và k <= 200000, a*b tối đa là 200000, nên int (tối đa ~2*10^9) là an toàn.