Tìm dãy con không chia hết cho một số nguyên

def find_subsequence(n, m, a):
    # Khởi tạo biến lưu kết quả
    max_length = 0
    max_subseq = []

    # Sinh ra tất cả các dãy con của dãy đã cho
    for i in range(1, 2**n):
        subseq = []
        sum_subseq = 0
        for j in range(n):
            if (i >> j) & 1:
                subseq.append(a[j])
                sum_subseq += a[j]

        # Kiểm tra xem dãy con này có thỏa mãn yêu cầu của bài toán hay không
        if len(subseq) > max_length and sum_subseq % m != 0:
            max_length = len(subseq)
            max_subseq = subseq

    # Trả về kết quả
    return max_length, max_subseq


# Đọc dữ liệu từ file
with open("MODM.INP", "r") as f:
    n, m = map(int, f.readline().split())
    a = list(map(int, f.readline().split()))

# Tìm kiếm dãy con thỏa mãn yêu cầu của bài toán
max_length, max_subseq = find_subsequence(n, m, a)

# Ghi kết quả vào file
with open("MODM.OUT", "w") as f:
    f.write(str(max_length) + "\n")
    f.write(" ".join(str(a.index(x)+1) for x in max_subseq))

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

int n, m, max_length;
vector<int> a, max_subseq;

void find_subsequence() {
    // Sinh tất cả các dãy con của dãy đã cho
    for (int i = 1; i < (1 << n); i++) {
        vector<int> subseq;
        int sum_subseq = 0;
        for (int j = 0; j < n; j++) {
            if ((i >> j) & 1) {
                subseq.push_back(a[j]);
                sum_subseq += a[j];
            }
        }

        // Kiểm tra xem dãy con này có thỏa mãn yêu cầu của bài toán hay không
        if (subseq.size() > max_length && sum_subseq % m != 0) {
            max_length = subseq.size();
            max_subseq = subseq;
        }
    }
}

int main() {
    // Đọc dữ liệu từ file
    freopen("MODM.INP", "r", stdin);
    cin >> n >> m;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // Tìm kiếm dãy con thỏa mãn yêu cầu của bài toán
    find_subsequence();

    // Ghi kết quả vào file
    freopen("MODM.OUT", "w", stdout);
    cout << max_length << endl;
    for (int i = 0; i < max_length; i++) {
        cout << find(a.begin(), a.end(), max_subseq[i]) - a.begin() + 1 << " ";
    }
    return 0;
}

# Đọc dữ liệu từ file
with open("MODM.INP", "r") as f:
    n, m = map(int, f.readline().split())
    a = list(map(int, f.readline().split()))

# Khởi tạo mảng đánh dấu để lưu các dãy con tìm được
dp = [[0 for _ in range(m)] for _ in range(n)]

# Tính toán các giá trị cho mảng đánh dấu
for i in range(n):
    # Trường hợp cơ sở: chỉ xét với phần tử đầu tiên của dãy con
    if a[i] % m != 0:
        dp[i][a[i] % m] = 1
    
    # Tìm các dãy con có chứa phần tử thứ i
    for j in range(i):
        for k in range(m):
            # Nếu dãy con tại vị trí j thỏa mãn điều kiện và
            # phần tử thứ i có thể thêm vào để tạo ra một dãy con mới
            if dp[j][k] != 0 and dp[i][(k + a[i]) % m] == 0:
                dp[i][(k + a[i]) % m] = dp[j][k] + 1

# Tìm dãy con có độ dài lớn nhất và không chia hết cho m
max_len = 0
max_subseq = []
for i in range(n):
    for j in range(m):
        if dp[i][j] > max_len and (j + a[i]) % m != 0:
            max_len = dp[i][j]
            max_subseq = [a[i]]
            k = j
            # Truy vết lại dãy con tìm được
            for l in range(i-1, -1, -1):
                if dp[l][k] == dp[i][j] - 1 and (k - a[l]) % m == j:
                    max_subseq.append(a[l])
                    k = (k - a[l]) % m
            max_subseq.reverse()

# Ghi kết quả vào file
with open("MODM.OUT", "w") as f:
    f.write(str(max_len) + "\n")
    f.write(" ".join(map(str, [a.index(x)+1 for x in max_subseq])))

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

const int MAXN = 100005;

int n, m;
int a[MAXN], f[MAXN], tr[MAXN];

int main() {
    freopen("MODM.INP", "r", stdin);
    freopen("MODM.OUT", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    memset(f, -1, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = m - 1; j >= 0; j--) {
            int r = (j - a[i] % m + m) % m;
            if (f[j] >= 0 && f[r] < 0) {
                f[r] = f[j] + 1;
                tr[r] = i;
            }
        }
        if (f[a[i] % m] < 0) {
            f[a[i] % m] = 1;
            tr[a[i] % m] = i;
        }
    }

    cout << f[0] << endl;
    vector<int> ans;
    for (int i = 0, j = 0; i != 0 || j != 1; j++) {
        if (f[i] == f[(i + a[tr[i]]) % m] + 1) {
            ans.push_back(tr[i]);
            i = (i + a[tr[i]]) % m;
        }
    }
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }

    return 0;
}