C++で全ペアのGCDから元の数値を復元する方法

概要

ある配列 array[] には、別の配列に含まれる要素同士の「すべての可能なペア」に対して計算されたGCD（最大公約数）の値が格納されています。本記事では、このGCD配列をもとに、計算に使われた元の数値を復元するアルゴリズムをC++で解説します。

入力例

array[] = {6, 1, 1, 13}

出力例

13 6
gcd(13, 13) = 13
gcd(13, 6) = 1
gcd(6, 13) = 1
gcd(6, 6) = 6

入力例（長いケース）

arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 6, 6, 8, 11, 13, 3, 3}

出力例

13 11 8 6 6

アルゴリズムの考え方

• まず、与えられた配列を降順にソートします。

• 最大の要素は必ず元の数値のひとつです。この数値を結果として保持し、配列から取り除きます。

• 直前のステップで確定した要素と、残りの要素（大きいものから順に）とのGCDを計算し、そのGCD値を出現頻度表から差し引いていきます。

動作のポイント

GCD配列には、同じ2つの数値のペアが順序違いとして2回ずつ含まれます。そこで、新しい数値を1つ確定するたびに、それまでに確定済みの各数値とのGCDを2つ分ずつ頻度表から減算します。こうすることで、すでに説明済みのペアを二重に数えることを防ぎ、頻度がまだ正のまま残っている要素だけが「未確定の元の数値」として検出できる仕組みです。

C++による実装例

// 手法のC++実装
#include <bits/stdc++.h>
using namespace std;

// 配列の内容を出力するユーティリティ関数
void printArr(int array[], int n1){
    for (int i = 0; i < n1; i++)
        cout << array[i] << " ";
}

// 元の数値を求める関数
void findNumbers(int array[], int n1){
    // 配列を降順にソート
    sort(array, array + n1, greater<int>());
    int freq1[array[0] + 1] = { 0 };
    // 各要素の出現回数をカウント
    for (int i = 0; i < n1; i++)
        freq1[array[i]]++;
    // 結果配列のサイズ
    int size1 = sqrt(n1);
    int brr1[size1] = { 0 }, x1, l1 = 0;
    for (int i = 0; i < n1; i++) {
        if (freq1[array[i]] > 0) {
            // 最も大きい要素を結果配列に格納
            brr1[l1] = array[i];
            // その要素の出現回数を1つ減らす
            freq1[brr1[l1]]--;
            l1++;
            for (int j = 0; j < l1; j++) {
                if (i != j) {
                    // GCDを計算
                    x1 = __gcd(array[i], brr1[j]);
                    // 該当するGCD値を2つ分減らす
                    freq1[x1] -= 2;
                }
            }
        }
    }
    printArr(brr1, size1);
}

// ドライバーコード
int main(){
    /* int array[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 6, 6, 6, 8, 11, 13, 3, 3}; */
    int array[] = { 6, 1, 1, 13};
    int n1 = sizeof(array) / sizeof(array[0]);
    findNumbers(array, n1);
    return 0;
}

出力

13 6