C++でLCM(arr[i], arr[j]) > min(arr[i], arr[j])を満たす配列内のペアを数える方法

この記事では、正の整数からなる配列が与えられたとき、LCM(arr[i], arr[j]) > min(arr[i], arr[j]) という条件を満たす要素ペアの個数を求める方法を解説します。つまり、ペアを構成する2つの要素の最小公倍数（LCM）が、そのうち小さい方の値より大きくなるようなペアを数えます。

注意： ペア (arr[i], arr[j]) と (arr[j], arr[i]) は同一のものとみなし、二重にカウントしてはいけません。

具体例で理解しよう

例1

入力： arr[] = [1, 5, 4, 2]

出力： 条件を満たすペアの数 ― 6

説明： 合計6つのペアが条件を満たします。

ペア1 (1,5)：LCM = 5 > 1
ペア2 (1,4)：LCM = 4 > 1
ペア3 (1,2)：LCM = 2 > 1
ペア4 (5,4)：LCM = 20 > 4
ペア5 (5,2)：LCM = 10 > 2
ペア6 (4,2)：LCM = 4 > 2

例2

入力： arr[] = [3, 3, 6]

出力： 条件を満たすペアの数 ― 2

説明： 合計2つのペアが条件を満たします。

ペア1 (3,6)：LCM = 6 > 3
ペア2 (3,6)：LCM = 6 > 3

アルゴリズムの考え方

実は、LCM(a, b) > min(a, b) という条件が成り立たないのは a == b の場合だけです。a ≠ b であれば、最小公倍数は必ず小さい方の値より大きくなります。

したがって、この問題は「異なる値からなるペアの総数」を求めることに帰着します。以下の手順で効率よく計算できます。

• まず、配列全体から作れる全ペア数を size × (size − 1) / 2 で求めます。
• 次に、unordered_map を使って各値の出現回数（頻度）を記録します。
• 各頻度 freq に対して、同一要素同士で作れるペア数 freq × (freq − 1) / 2 を計算し、合計します。
• 最後に「全ペア数 − 同一要素ペア数」を返せば答えになります。

この方法なら、各ペアのLCMを実際に計算する必要がなく、時間計算量 O(n) で解けます。

実装手順

• 整数型の配列を用意します。
• 関数 conditional_pair(int arr[], int size) は、配列とそのサイズを受け取り、条件を満たすペアの数を返します。
• 変数 count を 0 で初期化します。
• unordered_map<int, int> um を用意し、arr[] の各要素の出現頻度を記録します。
• 範囲ベース for ループでマップを走査し、各頻度 temp = it.second（it はイテレータ）について、temp × (temp − 1) / 2 を count に加算します。これは temp 個の同一要素から作れる全ペア数です。
• この時点で count には、考慮対象外となる「同一要素同士のペア」の総数が入っています。
• 配列全体の全ペア数を temp = size × (size − 1) / 2 として計算します。
• count を temp − count で更新します。
• count を結果として返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int conditional_pair(int arr[], int size){
    int count = 0;
    unordered_map<int, int> um;
    for (int i = 0; i < size; i++){
        um[arr[i]]++;
    }
    for (auto it : um){
        int temp = it.second;
        count = count + temp * (temp - 1) / 2;
    }
    int temp = (size * (size - 1)) / 2;
    count = temp - count;
    return count;
}
int main(){
    int arr[] = { 4, 1, 7, 3, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of pairs in an array such that LCM(arr[i], arr[j]) > min(arr[i],arr[j]) are:\n"<<conditional_pair(arr, size);
    return 0;
}

出力結果

上記のコードを実行すると、次のような出力が得られます。

Count of pairs in an array such that LCM(arr[i], arr[j]) > min(arr[i],arr[j]) are: 10

まとめ

LCM(a, b) > min(a, b) は a ≠ b のとき常に成立するため、本問題は「重複する値からなるペアを除外して数える」ことに帰着します。ハッシュマップで頻度を集計し、全ペア数から同一要素ペア数を差し引くだけで答えが求まり、時間計算量 O(n)・空間計算量 O(n) と非常に効率的な解法です。