Hiểu bài toán

Bài toán yêu cầu đếm số lượng số nguyên dương là bội của N và không vượt quá X. Với mỗi test case, ta được cho hai số nguyên dương N và X. Số lượng bội của N không vượt quá X chính là số thương của phép chia X cho N (tức X / N theo toán học, floor division). Ví dụ, nếu N=3, X=10, các bội là 3, 6, 9, vậy đáp án là 3. Xét thương 10/3 = 3.33... -> floor là 3.

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

Cách Sử dụng phép chia nguyên

#include <iostream>
using namespace std;

int main() {
    int K;
    cin >> K; 
    while (K--) {
        long long N, X;
        cin >> N >> X;
        long long count = X / N;
        cout << count << endl;
    }
    return 0;
}

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

Đây là cách tiếp cận trực tiếp và hiệu quả nhất. Trong C++, phép chia hai số nguyên (long long) sẽ tự động thực hiện phép chia lấy phần nguyên (floor division). Với mỗi test case, ta chỉ cần thực hiện phép chia X / N và in ra kết quả. Độ phức tạp thời gian phụ thuộc vào số lượng test case K, mỗi test case xử lý trong thời gian hằng số O(1).

Cách Sử dụng vòng lặp (Brute Force)

#include <iostream>
using namespace std;

int main() {
    int K;
    cin >> K;
    while (K--) {
        long long N, X;
        cin >> N >> X;
        long long count = 0;
        for (long long i = N; i <= X; i += N) {
            count++;
        }
        cout << count << endl;
    }
    return 0;
}

• Time Complexity: O(X/N)
• Space Complexity: O(1)

Cách này mô phỏng lại việc đếm các bội bằng cách lặp từ N, 2N, 3N... đến khi vượt quá X. Mặc dù đúng về mặt logic nhưng nó rất chậm nếu X lớn (ví dụ X=10^18) vì số vòng lặp có thể lên tới 10^18. Đây là cách tiếp cận không tối ưu và dễ gây Time Limit Exceeded.

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

Bài học kinh nghiệm

• Vấn đề 'đếm số lượng bội không vượt quá X' tương đương với việc tính toán thương số nguyên floor(X / N).
• Sử dụng kiểu dữ liệu long long là cần thiết để tránh tràn số (overflow) vì X có thể lên tới 10^18.
• Phép chia lấy phần nguyên trong C++ cho các số nguyên dương là một thao tác CPU cực kỳ nhanh, giúp giải quyết bài toán ngay lập tức.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu int hoặc unsigned int cho N và X có thể gây tràn số nếu giá trị đầu vào lớn hơn 2*10^9.
• Viết nhầm biểu thức: ví dụ (X - 1) / N hoặc X / (N + 1) sẽ cho kết quả sai lệch so với yêu cầu bài toán (đếm các bội <= X).