【C++】配列内の倍数の個数を求めるクエリ処理の実装方法

この記事では、整数型の配列 arr[] と、それぞれ値 m を持つ Q 個のクエリが与えられたとき、「配列内に m の倍数がいくつ含まれているか」を答えるプログラムを C++ で実装する方法を解説します。

問題の概要

各クエリに対して、配列内の要素のうち m で割り切れるもの(すなわち m の倍数)の個数を数えて出力します。

具体例で確認してみましょう。

入力:arr[] = {4, 7, 3, 8, 12, 15}
Q = 3、query[] = {2, 3, 5}

出力:3 3 1

出力の解説

クエリ1:m = 2 のとき、配列内の倍数は 4, 8, 12 の 3 つなので、個数は 3。

クエリ2:m = 3 のとき、配列内の倍数は 3, 12, 15 の 3 つなので、個数は 3。

クエリ3:m = 5 のとき、配列内の倍数は 15 のみなので、個数は 1。

解法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

この解法では、1 回のクエリにつき配列を 1 回走査するため、時間計算量は O(Q×n) となります。クエリの数や配列のサイズが大きくなるほど処理が遅くなる点が課題です。

解法2:前計算による高速化(篩の考え方を応用)

より効率的なのが、エラトステネスの篩のような発想で倍数の個数を事前に計算しておく方法です。まず配列内の各値の出現回数を数え、次に 1 から配列の最大値までの各整数 i について「i の倍数に該当する要素の合計個数」を前計算します。こうしておけば、各クエリには前計算済みの配列を参照するだけで即座に答えられるようになります。

サンプルコード

#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

2つの解法の比較

前計算方式では、配列の最大値を M とすると、前計算に必要な時間は約 O(M log M)、その後の各クエリへの回答は O(1) で済みます。そのため、クエリの件数が多い場合や、同じ配列に対して何度も問い合わせを行う場合には、こちらの手法が圧倒的に有利です。一方で、配列の最大値が非常に大きい場合は前計算用のメモリが必要になるため、データの規模に応じて適切な手法を選択することが重要です。