Hiểu bài toán

Bài toán yêu cầu đếm số lượng số nguyên dương trong một mảng A có số lượng ước số nhỏ hơn K. Với mỗi test case, chúng ta nhận vào N (số lượng phần tử), K (giới hạn số ước), và mảng A gồm N số nguyên. Chúng ta cần trả về số lượng số trong mảng thỏa mãn điều kiện số ước < K. Ví dụ, với K=3, các số 1 (1 ước), 2 (2 ước), 3 (2 ước) đều thỏa mãn, còn 4 (3 ước) thì không.

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

Cách Sàng số ước (Sơ đồ Eratosthenes mở rộng)

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

const int N = 1e6 + 7;
vector<int> slu(N, 2);

void sang() {
    slu[0] = 1;
    slu[1] = 1;
    for (int i = 2; i < N; i++) {
        for (int j = i * 2; j < N; j += i) {
            slu[j]++;
        }
    }
}

int main() {
    sang();
    int t; cin >> t;
    for (int ii = 1; ii <= t; ii++) {
        int n, k;
        cin >> n >> k;
        int dem = 0;
        for (int i = 0; i < n; i++) {
            int x; cin >> x;
            if (slu[x] < k) dem++;
        }
        cout << "Case #" << ii << ": " << dem << '\n';
    }
    return 0;
}

• Time Complexity: O(M log M + T*N) ~ 10^8, với M=10^6
• Space Complexity: O(M)

Phương pháp này tiền xử lý số lượng ước cho tất cả các số từ 1 đến 10^6 trước. Dùng mảng slu với giá trị ban đầu là 2 (vì mọi số > 1 đều có ít nhất 2 ước là 1 và chính nó). Duyệt i từ 2 đến MAX, với mỗi i, ta duyệt các bội số j của nó (j = 2i, 3i...) và tăng slu[j] lên 1. Cuối cùng, với mỗi truy vấn, ta chỉ cần tra cứu mảng slu để kiểm tra điều kiện. Đây là phương pháp tối ưu nhất về thời gian chạy cho các test case lặp lại.

Cách Sàng số ước (Tối ưu)

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

const int MAX = 1e6 + 1;
int DemUoc[MAX] = {0};

void giai() {
    for (int i = 1; i < MAX; i++) {
        for (int j = i; j < MAX; j += i) {
            DemUoc[j]++;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T, dem = 1;
    cin >> T;
    giai();
    while (T--) {
        int n, k;
        cin >> n >> k;
        int x, res = 0;
        for (int i = 0; i < n; i++) {
            cin >> x;
            if (DemUoc[x] < k) {
                res++;
            }
        }
        cout << "Case #" << dem++ << ": " << res << "\n";
    }
    return 0;
}

• Time Complexity: O(M log M + T*N)
• Space Complexity: O(M)

Đây là biến thể của phương pháp sàng ước. Cách viết này bắt đầu vòng lặp từ i=1 (vì số 1 là ước của mọi số) và gán giá trị ban đầu cho mảng là 0. Logic tính toán số ước là hoàn toàn giống nhau. Việc sử dụng ios::sync_with_stdio(false) và cin.tie(nullptr) giúp tăng tốc độ nhập xuất dữ liệu, rất quan trọng trong lập trình thi đấu khi dữ liệu lớn.

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

Bài học kinh nghiệm

• Bài toán có nhiều test case và các số A_i bị giới hạn trong khoảng [1, 10^6]. Điều này gợi ý我们应该使用 tiền xử lý (precomputation) để tính số ước cho các số này một lần duy nhất, thay vì tính toán lại cho mỗi test case.
• Thuật toán sàng số ước (hoặc tích trâu) có độ phức tạp O(N log N) với N là giới hạn giá trị (10^6), cho phép tính trước kết quả cho mọi số có thể xuất hiện trong input.
• Sau khi có mảng số ước tiền xử lý, mỗi test case chỉ mất O(N) để đếm số lượng số thỏa mãn.

Lỗi thường gặp

• Quên khởi tạo hoặc sai lệch giá trị ban đầu của mảng số ước (ví dụ: số 0 và số 1 có số ước bằng 1, các số khác >= 2). Solution 1 sai khi gán mặc định là 2.
• Tối ưu hóa I/O (iosbase::syncwith_stdio(false); cin.tie(NULL);) thường bị bỏ qua dẫn đến Time Limit Exceeded.
• Nếu sử dụng giải pháp không tiền xử lý (tính số ước cho từng số bằng cách duyệt từ 1 đến sqrt(x)), độ phức tạp sẽ là O(T * N * sqrt(A_i)), cao hơn nhiều so với O(T * N + M log M) của sàng.