นับ Subarray ที่ผลคูณหาร k ลงตัว ใน C++

โจทย์: ให้อาร์เรย์ arr[] และจำนวนเต็ม k ต้องการนับจำนวน Subarray ที่ผลคูณขององค์ประกอบหาร k ลงตัว

ตัวอย่าง

arr = {2, 1, 5, 8}, k = 4
Subarray ที่ถูกต้อง: [8], [5,8], [1,5,8], [2,1,5,8] → 4 subarrays

วิธีที่ 1: Naive Approach (O(n³))

ตรวจสอบทุก subarray คำนวณผลคูณตรวจสอบหาร k ลงตัว

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 *= arr[k];
            if (temp % k == 0) count++;
        }
    }
    return count;
}

วิธีที่ 2: Efficient Approach ด้วย Segment Tree (O(n² log n))

สร้าง Segment Tree เก็บผลคูณ modulo k แล้ว query ผลคูณของ subarray ใดๆ ได้ใน O(log n)

#define MAX_SIZE 100002
int seg_tree[4 * MAX_SIZE];

void build(int node, int l, int r, const int* arr, int k) {
    if (l == r) {
        seg_tree[node] = (1LL * arr[l]) % k;
        return;
    }
    int mid = (l + r) >> 1;
    build(2*node, l, mid, arr, k);
    build(2*node+1, mid+1, r, arr, k);
    seg_tree[node] = (seg_tree[2*node] * seg_tree[2*node+1]) % k;
}

int query(int node, int l, int r, int ql, int qr, int k) {
    if (l > r || l > qr || r < ql) return 1;
    if (l >= ql && r <= qr) return seg_tree[node] % k;
    int mid = (l + r) >> 1;
    int left = query(2*node, l, mid, ql, qr, k);
    int right = query(2*node+1, mid+1, r, ql, qr, k);
    return (left * right) % k;
}

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

ตัวอย่างรัน

int main() {
    int arr[] = {2, 1, 5, 8, 10, 12};
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << "Count: " << product_k(arr, size, k);
    return 0;
}

ผลลัพธ์

Count of sub-arrays whose product is divisible by k are: 18

หมายเหตุ: วิธี Segment Tree เร็วกว่าเมื่อมีหลาย query แต่สำหรับโจทย์นี้ที่ต้องตรวจสอบทุก subarray ยังคงเป็น O(n² log n) สามารถปรับปรุงเป็น O(n log n) ได้ด้วยการแยกตัวประกอบเฉพาะของ k