在C ++中查询数组中的倍数计数

在这个问题中，我们给了arr []和Q个查询，每个查询都包含一个值m。我们的任务是创建一个程序来解决C ++中数组中的倍数计数查询。

问题描述

为了解决查询，我们需要计算所有m的倍数。为此，我们将检查可被m整除的元素。

让我们举个例子来了解这个问题，

输入：arr [] = {4，7，3，8，12，15}

Q = 3查询[] = {2，3，5}

输出：3 3 1

说明

查询1：m = 2，数组中的倍数= 4，8，12 Count = 3。

查询2：m = 3，数组中的倍数= 3、12、15。计数= 3。

查询3：m = 5，数组中的倍数=15。计数= 1。

解决方法

一个简单的解决方案是遍历每个查询值的数组并计算被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）的每个查询遍历一次数组。

更好的解决方案是使用Eratosthenes筛子查找所有多个

和给定数组的元素计数。这个想法是预先计算所有元素的倍数，直到数组的最大值。然后调用预先计算的数组以查找查询的倍数计数。

示例

#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