Pythonのすべてのペアのgcd（）から元の番号を検索します

別の配列の要素の可能なすべてのペアのGCDが与えられている配列Aがあるとすると、与えられたGCD配列の計算に使用される元の数値を見つける必要があります。

したがって、入力がA =[6、1、1、13]の場合、gcd（13、13）は13、gcd（13、6）は1、gcd（ 6、13）は1、gcd（6、6）は6

これを解決するには、次の手順に従います-

• n：=Aのサイズ

• 配列Aを降順で並べ替えます

• オカレンス：=サイズA[0]の配列で0で埋める

• 0からnの範囲のiの場合、実行

  • オカレンス[A[i]]：=オカレンス[A [i]] + 1

• サイズ：=nの平方根の整数

• res：=Aのサイズと同じサイズの配列で、0で埋める

• l：=0

• 0からnの範囲のiの場合、実行

  • オカレンス[A[i]]>0の場合、

    • res [l]：=A [i]

    • オカレンス[res[l]]：=オカレンス[res [l]]-1

    • l：=l + 1

    • 0からlの範囲のjについては、次のようにします

      • iがjと同じでない場合、

        • g：=gcd（A [i]、res [j]）

        • オカレンス[g]：=オカレンス[g]-2

• res[インデックス0からサイズ]を返す

例

理解を深めるために、次の実装を見てみましょう-

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]