การสืบค้นจำนวนตัวคูณในอาร์เรย์ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] และ Q queries แต่ละ query มีค่า m ภารกิจคือการสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นจำนวนตัวคูณในอาร์เรย์ใน C++

คำอธิบายปัญหา

สำหรับการแก้ query เราต้องนับตัวเลขทั้งหมดที่เป็นตัวคูณของ m โดยตรวจสอบว่าองค์ประกอบไหนหารด้วย m ลงตัว

ตัวอย่างเพื่อเข้าใจปัญหา

อินพุต: arr[] = {4, 7, 3, 8, 12, 15}

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

เอาต์พุต: 3 3 1

คำอธิบาย

Query 1: m = 2, ตัวคูณในอาร์เรย์ = 4, 8, 12 จำนวน = 3

Query 2: m = 3, ตัวคูณในอาร์เรย์ = 3, 12, 15 จำนวน = 3

Query 3: m = 5, ตัวคูณในอาร์เรย์ = 15 จำนวน = 1

แนวทางแก้ปัญหา

วิธีง่ายคือการวนลูปผ่านอาร์เรย์สำหรับแต่ละค่า query และนับจำนวนองค์ประกอบที่หารด้วย m ลงตัว

ตัวอย่างโปรแกรม (วิธีแบบง่าย)

#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;
}

เอาต์พุต

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

วิธีนี้มีความซับซ้อนด้านเวลา O(Q×n)

วิธีที่ดีกว่า คือการใช้ Sieve of Eratosthenes เพื่อหาตัวคูณทั้งหมดและจำนวนองค์ประกอบสำหรับอาร์เรย์ที่กำหนด แนวคิดคือคำนวณล่วงหน้าจำนวนตัวคูณของทุกองค์ประกอบจนถึงค่าสูงสุดของอาร์เรย์ แล้วเรียกใช้อาร์เรย์ที่คำนวณไว้เพื่อหาจำนวนตัวคูณสำหรับ queries

ตัวอย่างโปรแกรม (วิธี Sieve/Precomputation)

#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;
}

เอาต์พุต

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