Phần tử mảng không chia hết cho bất kỳ phần tử nào của mảng khác trong C++

Cho 2 mảng arr1[] (kích thước n) và arr2[] (kích thước m). Tìm các phần tử trong arr1 mà **không chia hết** cho **bất kỳ** phần tử nào trong arr2.

Ví dụ

Đầu vào: arr1 = {17, 15, 5, 12, 8}, arr2 = {5, 4}

Đầu ra: 17

Giải thích: 15,5 chia hết cho 5. 12,8 chia hết cho 4. 17 không chia hết cho 5 cũng không chia hết cho 4.

Phương pháp giải

Cách 1: Naive O(N*M) - Duyệt từng cặp (a trong arr1, b trong arr2). Kiểm tra a % b == 0.

Cách 2: Tối ưu O(N + M + MaxLogMax) - Sàng đánh dấu bội số (Tương tự Sieve).

1. Tìm maxVal = max(arr1).
2. Tạo mảng isMultiple[maxVal+1] khởi tạo false.
3. Với mỗi x trong arr2: Đánh dấu isMultiple[k] = true cho mọi bội số k của x (k = x, 2x, 3x... ≤ maxVal).
4. Duyệt arr1: Nếu isMultiple[arr1[i]] == false => In ra.

Chương trình minh họa (Cách 2 - Tối ưu)

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

void findNonDivisible(int arr1[], int n, int arr2[], int m) {
    int maxVal = 0;
    for (int i = 0; i < n; i++) maxVal = max(maxVal, arr1[i]);
    
    vector<bool> isMultiple(maxVal + 1, false);
    
    // Đánh dấu bội số của các phần tử arr2
    for (int i = 0; i < m; i++) {
        int x = arr2[i];
        if (x == 0) continue; // Tránh chia cho 0
        for (int j = x; j <= maxVal; j += x) {
            isMultiple[j] = true;
        }
    }
    
    cout << "Cac phan tu khong chia het cho bat ky phan tu nao cua arr2: ";
    bool found = false;
    for (int i = 0; i < n; i++) {
        if (!isMultiple[arr1[i]]) {
            cout << arr1[i] << " ";
            found = true;
        }
    }
    if (!found) cout << "Khong co";
}

int main() {
    int arr1[] = {17, 15, 5, 12, 23, 8};
    int arr2[] = {5, 4};
    int n = sizeof(arr1)/sizeof(arr1[0]);
    int m = sizeof(arr2)/sizeof(arr2[0]);
    findNonDivisible(arr1, n, arr2, m);
    return 0;
}

Đầu ra

Cac phan tu khong chia het cho bat ky phan tu nao cua arr2: 17 23