Pythonで全ペアのGCDから元の配列を復元する方法

問題の概要

ある配列Aが与えられたとします。この配列の各要素は、別の配列（元の配列）から選んだ2つの要素のペアごとに計算した最大公約数（GCD）に対応しています。私たちの課題は、このGCD配列をもとに、計算に使用された元の数値を復元することです。

例として、入力が A = [6, 1, 1, 13] の場合を考えてみましょう。このときの出力は [13, 6] となります。理由は以下の通りです。

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

アルゴリズムの鍵となる考え方

このアルゴリズムのポイントは、「GCD配列の中で最も大きい値は、元の配列の最大値とそれ自身のGCDに等しい」という性質を利用することです。そのため、配列を降順にソートして先頭から処理を進めれば、確実に元の配列の要素を特定できます。各要素を確定するたびに、すでに確定済みの要素とのGCDを計算し、対応する出現回数を減らしていくことで、重複なく正しく復元できます。

解決手順

この問題を解くには、次の手順に従います。

1. n := Aのサイズとします。
2. 配列Aを降順にソートします。
3. occurrence := サイズがA[0]+1の配列を作成し、すべて0で初期化します。
4. i を 0 から n-1 まで繰り返します。
   • occurrence[A[i]] := occurrence[A[i]] + 1
5. size := nの平方根の整数部分とします。
6. res := Aと同じサイズの配列を作成し、すべて0で初期化します。
7. l := 0 とします。
8. i を 0 から n-1 まで繰り返します。
   • もし occurrence[A[i]] > 0 であれば:
     • res[l] := A[i]
     • occurrence[res[l]] := occurrence[res[l]] - 1
     • l := l + 1
     • j を 0 から l-1 まで繰り返します。
       • もし i と j が異なる場合:
         • g := gcd(A[i], res[j])
         • occurrence[g] := occurrence[g] - 2
9. res のインデックス 0 から size までを結果として返します。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

from math import sqrt, gcd

def get_actual_array(A):
    n = len(A)
    A.sort(reverse=True)
    occurrence = [0 for i in range(A[0] + 1)]
    for i in range(n):
        occurrence[A[i]] += 1
    size = int(sqrt(n))
    res = [0 for i in range(len(A))]
    l = 0
    for i in range(n):
        if (occurrence[A[i]] > 0):
            res[l] = A[i]
            occurrence[res[l]] -= 1
            l += 1
            for j in range(l):
                if (i != j):
                    g = gcd(A[i], res[j])
                    occurrence[g] -= 2
    return res[:size]

A = [6, 1, 1, 13]
print(get_actual_array(A))

入力

[6, 1, 1, 13]

出力

[13, 6]