Đếm tập con thỏa mãn điều kiện chia hết trong C++

Cho mảng arr[] và số x. Đếm tập con mà mọi phần tử và tổng của tập con đều chia hết cho x.

Ý tưởng

• Đếm số phần tử trong mảng chia hết cho x, gọi là count.
• Số tập con thỏa mãn = 2^count - 1 (trừ tập rỗng).
• Nếu x = 1 thì tất cả phần tử đều chia hết, kết quả = 2^n - 1.

Ví dụ hoàn chỉnh

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int sub_sets(int arr[], int size, int val) {
    int count = 0;
    if (val == 1) {
        count = pow(2, size) - 1;
        return count;
    }
    for (int i = 0; i < size; i++) {
        if (arr[i] % val == 0)
            count++;
    }
    count = pow(2, count) - 1;
    return count;
}

int main() {
    int arr[] = {4, 6, 1, 3, 8, 10, 12}, val = 4;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Số tập con thỏa mãn: " << sub_sets(arr, size, val);
    return 0;
}

Kết quả

Số tập con thỏa mãn: 7