Truy vấn đếm bội số trong mảng trong C++

Trong bài toán này, ta được cho mảng arr[] và Q truy vấn, mỗi truy vấn gồm một giá trị m. Nhiệm vụ: tạo chương trình giải quyết truy vấn đếm bội số trong mảng trong C++.

Mô tả bài toán

Với mỗi truy vấn, đếm tất cả số là bội của m, tức các phần tử chia hết cho m.

Ví dụ minh họa

Đầu vào: arr[] = {4, 7, 3, 8, 12, 15}

Q = 3, query[] = {2, 3, 5}

Đầu ra: 3 3 1

Giải thích

Truy vấn 1: m = 2, bội số trong mảng = 4, 8, 12. Đếm = 3.

Truy vấn 2: m = 3, bội số = 3, 12, 15. Đếm = 3.

Truy vấn 3: m = 5, bội số = 15. Đếm = 1.

Phương pháp giải

Cách đơn giản: duyệt mảng cho mỗi truy vấn, đếm phần tử chia hết cho m.

Ví dụ

#include <iostream>
using namespace std;

int solveQuery(int arr[], int N, int m) {
    int count = 0;
    for(int i = 0; i < N; i++) {
        if(arr[i] % m == 0)
            count++;
    }
    return count;
}

int main() {
    int arr[] = {4, 7, 3, 8, 12, 15};
    int N = sizeof(arr)/sizeof(arr[0]);
    int Q = 3;
    int query[] = {2, 3, 5};
    for(int i = 0; i < Q; i++)
        cout << "The count of multiples in array " << solveQuery(arr, N, query[i]) << endl;
    return 0;
}

Đầu ra

The count of multiples in array 3
The count of multiples in array 3
The count of multiples in array 1

Độ phức tạp O(Q×n).

Cách tốt hơn: dùng Sàng Eratosthenes biến thể để tiền tính số bội của mọi giá trị đến max(mảng). Ý tưởng: đếm tần suất mỗi giá trị trong mảng, sau đó với mỗi i từ 1 đến maxVal, duyệt các bội j của i và cộng tần suất vào preCalcCount[i].

Ví dụ

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

int preCalcCount[10001];

void PreCalculateMultiples(int arr[], int N) {
    int maxVal = *max_element(arr, arr + N);
    int count[maxVal + 1];
    memset(count, 0, sizeof(count));
    memset(preCalcCount, 0, (maxVal + 1) * sizeof(int));
    for (int i = 0; i < N; ++i)
        ++count[arr[i]];
    for (int i = 1; i <= maxVal; ++i)
        for (int j = i; j <= maxVal; j += i)
            preCalcCount[i] += count[j];
}

int main() {
    int arr[] = {4, 7, 3, 8, 12, 15};
    int N = sizeof(arr)/sizeof(arr[0]);
    int Q = 3;
    int query[Q] = {2, 3, 5};
    PreCalculateMultiples(arr, N);
    for(int i = 0; i < Q; i++)
        cout << "The count of multiples in array " << preCalcCount[query[i]] << endl;
    return 0;
}

Đầu ra

The count of multiples in array 3
The count of multiples in array 3
The count of multiples in array 1