Python의 모든 쌍에서 gcd()에서 원래 숫자 찾기

다른 배열의 모든 가능한 요소 쌍에 대한 GCD가 제공된 배열 A가 있다고 가정하면 주어진 GCD 배열을 계산하는 데 사용되는 원래 숫자를 찾아야 합니다.

따라서 입력이 A =[6, 1, 1, 13]과 같으면 출력은 [13, 6]이 됩니다. 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으로 채움

• 내가 :=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]