Đếm mảng con có tích chia hết cho k trong C++

Cho mảng arr[] và số k, đếm số mảng con có tích phần tử chia hết cho k.

Cách 1: Naive (O(n³))

Ba vòng lặp lồng: chọn đầu, cuối, tính tích, kiểm tra chia hết.

Cách 2: Hiệu quả với Segment Tree (O(n² log n))

• Xây dựng segment tree lưu tích modulo k.
• Truy vấn tích trên đoạn [i, j] trong O(log n).
• Duyệt mọi cặp (i, j), nếu tích % k == 0 thì đếm.

Ví dụ Naive

int product_k(int arr[], int size, int k) {
    int count = 0;
    for (int i = 0; i < size; i++) {
        for (int j = i; j < size; j++) {
            int temp = 1;
            for (int k = i; k <= j; k++)
                temp = temp * arr[k];
            if (temp % k == 0)
                count++;
        }
    }
    return count;
}

Ví dụ Segment Tree

#define size_2 100002
int arr_2[4 * size_2];

void set_in(int fit, int first, int last, const int* arr, int k) {
    if (first == last) {
        arr_2[fit] = (1LL * arr[first]) % k;
        return;
    }
    int level = (first + last) >> 1;
    set_in(2 * fit, first, level, arr, k);
    set_in(2 * fit + 1, level + 1, last, arr, k);
    arr_2[fit] = (arr_2[2 * fit] * arr_2[2 * fit + 1]) % k;
}

int check(int fit, int first, int last, int start, int end, int k) {
    if (first > last || first > end || last < start)
        return 1;
    if (first >= start && last <= end)
        return arr_2[fit] % k;
    int level = (first + last) >> 1;
    int set_1 = check(2 * fit, first, level, start, end, k);
    int set_2 = check(2 * fit + 1, level + 1, last, start, end, k);
    return (set_1 * set_2) % k;
}

Kết quả mẫu

arr[] = {2, 1, 5, 8}, k=4 → 4 mảng con
arr[] = {7, 1, 9, 7}, k=9 → 6 mảng con