Hiểu bài toán

Bài toán yêu cầu xử lý các truy vấn trên một dãy số A. Với mỗi truy vấn (L, R, K), ta cần đếm số lượng chỉ số i ∈ [L, R] sao cho A[i] chia hết cho K hoặc A[i] là bội của K (tức K chia hết cho A[i]). Nói cách khác, ta cần đếm số phần tử trong đoạn [L, R] mà có giá trị là ước hoặc bội của K. Dữ liệu: N, Q ≤ 2×10^5, giá trị A[i] ≤ 2×10^5.

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

Cách Brute Force

void solve_query_brute(int L, int R, int K) {
    int count = 0;
    for (int i = L; i <= R; i++) {
        if (A[i] % K == 0 || K % A[i] == 0) {
            count++;
        }
    }
    cout << count << "\n";
}

• Time Complexity: O(Q * N)
• Space Complexity: O(N)

Với mỗi truy vấn, duyệt qua tất cả các chỉ số từ L đến R và kiểm tra điều kiện. Cách này đơn giản nhưng quá chậm với N, Q lớn (2×10^5 * 2×10^5 = 4×10^10 thao tác).

Cách Precompute Divisors & Multiples (Full)

vector<int> pos[200005];
for (int i = 1; i <= n; i++) {
    int x = a[i];
    // Thêm chỉ số i vào các ước của x
    for (int d = 1; d * d <= x; d++) {
        if (x % d == 0) {
            pos[d].push_back(i);
            if (d * d != x) pos[x / d].push_back(i);
        }
    }
    // Thêm chỉ số i vào các bội của x
    for (int m = 2 * x; m <= 200000; m += x) {
        pos[m].push_back(i);
    }
}
for (int i = 1; i <= 200000; i++) {
    sort(pos[i].begin(), pos[i].end());
}
// Query: Dùng binary search trên pos[K] để đếm số phần tử trong [L, R]
auto it1 = lower_bound(pos[K].begin(), pos[K].end(), L);
auto it2 = upper_bound(pos[K].begin(), pos[K].end(), R);
cout << distance(it1, it2) << "\n";

• Time Complexity: O(N sqrt(M) log N + M log M + Q log N)
• Space Complexity: O(N sqrt(M) + M)

Ta precompute cho mỗi giá trị K (từ 1 đến 200,000) danh sách các chỉ số i mà A[i] chia hết cho K hoặc K chia hết cho A[i].

1. Để lấy các ước của A[i], ta dùng vòng lặp sqrt(A[i]).
2. Để lấy các bội của A[i], ta lặp qua các bội của A[i] nhỏ hơn 200,000.
3. Sau đó sort các danh sách và dùng binary search để trả lời truy vấn. Độ phức tạp xây dựng: Với mỗi A[i], số ước là O(sqrt(M)), số bội là O(M/A[i]). Tổng quãng thời gian xây dựng là O(N * sqrt(M) + M * log M). Độ phức tạp truy vấn: O(log N).

Cách Offline Query Decomposition (Mo's Algorithm)

// Cấu trúc truy vấn
struct Query {
    int l, r, k, id;
};

// Khai báo全局变量
int freq[200005]; // Tần suất xuất hiện của các giá trị trong đoạn hiện tại
int cnt[200005]; // cnt[t] = số lượng số trong đoạn có đúng t ước/bội (tính toán tạm)
int current_ans = 0;

void add(int val) {
    // Khi thêm một số val vào đoạn, nó có thể ảnh hưởng đến các truy vấn K mà nó là ước/bội.
    // Tuy nhiên, Mo's Algorithm không xử lý trực tiếp bài toán này tốt vì mỗi phần tử ảnh hưởng đến nhiều K.
    // Code này chỉ mang tính chất minh họa logic Mo thông thường, không áp dụng trực tiếp vào bài này.
    // Thực tế, giải pháp Mo cho bài này phải dùng kỹ thuật 'update query' hoặc offline trên K.
}

int main() {
    // ... (đọc input)
    // Đây là một bài toán khó apply Mo's Algorithm trực tiếp.
    // Phải chia nhỏ theo K hoặc dùng cấu trúc dữ liệu phức tạp.
}

• Time Complexity: O((N + Q) sqrt(N) * Cost)
• Space Complexity: O(N + Q)

Mo's Algorithm thường dùng cho bài toán đếm phần tử thỏa mãn điều kiện trong đoạn. Tuy nhiên, điều kiện ở đây phụ thuộc vào K (mỗi truy vấn có K khác nhau). Nếu dùng Mo, ta phải duy trì tần suất các giá trị A[i] trong đoạn. Với mỗi truy vấn, ta phải duyệt qua các ước/bội của K để cộng dồn, hoặc duyệt qua các phần tử trong đoạn. Độ phức tạp: O((N+Q) * sqrt(N) * Cost). Nếu Cost là kiểm tra ước/bội (sqrt(M)), thì tổng là O((N+Q) * sqrt(N) * sqrt(M)) ~ 10^10, quá chậm. Nếu Cost là duyệt qua các phần tử trong đoạn (O(N)), cũng quá chậm. Vì vậy, Mo's Algorithm không phải là lựa chọn tốt ở đây trừ khi kết hợp với các tối ưu khác (như chia nhỏ theo K hoặc dùng Fenwick Tree hỗ trợ).

Cách Optimization: Precompute Queries by K

// Tương tự Solution 2 & 3
// 1. Đọc Q truy vấn và lưu lại theo từng giá trị K.
// 2. Với mỗi K, ta cần đếm các chỉ số i sao cho A[i] | K hoặc K | A[i].
// 3. Thay vì precompute cho tất cả K (kém hiệu quả memory/time nếu dùng full M*N),
//    ta có thể chỉ precompute cho các K xuất hiện trong truy vấn.
//    Tuy nhiên, Solution 2 lại precompute full cho tất cả các số từ 1 đến M.
//    Điều này có thể chấp nhận được vì M = 200,000.

// Code Solution 2 đã cung cấp logic này:
// - Duyệt A[i], thêm i vào các ước và bội của A[i].
// - Sau đó sort và dùng binary search cho từng K trong truy vấn.

void solve_optimized() {
    // Input
    // Precompute: pos[x] chứa các chỉ số i mà A[i] là ước/bội của x
    // Query: Dùng binary search trên pos[K]
}

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

Đây là phương pháp tối ưu nhất được đề xuất trong các solutions.

• Preprocessing: Duyệt qua từng phần tử A[i]. Với mỗi A[i], ta xác định các số K mà A[i] là ước hoặc bội của K (tức là A[i] chia hết cho K hoặc K chia hết cho A[i]).
  • Nếu A[i] là ước của K: K là bội của A[i]. Ta thêm chỉ số i vào vector pos[K] cho mọi bội K của A[i] (dưới MAX_VAL).
  • Nếu K là ước của A[i]: K là ước của A[i]. Ta thêm chỉ số i vào vector pos[K] cho mọi ước K của A[i].
  • Trong code, tác giả đã làm ngược lại một chút nhưng cùng logic: duyệt A[i], thêm i vào p[d] (nếu d là ước) và p[m] (nếu m là bội).
• Query: Với truy vấn (L, R, K), ta chỉ cần tìm số lượng chỉ số trong pos[K] nằm trong đoạn [L, R] bằng binary search.
• Complexity: Vòng lặp bội là O(M log M), vòng lặp ước là O(N * sqrt(M)). Tổng cộng chấp nhận được với M=200,000.

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

Bài học kinh nghiệm

• Bài toán có thể đổi hình thức: Thay vì hỏi với mỗi K, đếm A[i] thỏa mãn, ta có thể precompute cho mỗi giá trị V, danh sách các K mà V thỏa mãn điều kiện (tức V là ước hoặc bội của K). Sau đó lưu trữ các chỉ số i của V vào K.
• Giá trị A[i] và K đều giới hạn trong khoảng [1, 200,000], cho phép ta sử dụng mảng (array) để lưu trữ danh sách chỉ số cho mỗi giá trị K.
• Binary Search là công cụ đắc lực để đếm số lượng phần tử trong đoạn [L, R] của một mảng đã được sắp xếp.

Lỗi thường gặp

• Lặp qua các bội của A[i] (m = 2A[i], 3A[i]...) có độ phức tạp O(M/A[i]). Nếu làm ngược lại (với mỗi K, kiểm tra K chia hết cho A[i] hay không) độ phức tạp sẽ là O(M*N), quá chậm. Phải lặp theo chiều của A[i] để cập nhật K.
• Quên sort danh sách chỉ số trước khi dùng binary search.
• Làm sai giới hạn vòng lặp bội (phải nhỏ hơn hoặc bằng MAX_VAL).