Python에서 서로 다른 하위 시퀀스 GCD의 수를 찾는 프로그램

<시간/>

양수 값을 가진 배열 num이 있다고 가정합니다. nums의 비어 있지 않은 모든 하위 시퀀스 중에서 서로 다른 GCD의 수를 찾아야 합니다. 우리가 알고 있듯이 숫자 시퀀스의 GCD는 시퀀스의 모든 숫자를 균등하게 나누는 가장 큰 값입니다.

따라서 입력이 nums =[4,6,18]과 같으면 gcd([4]) =4, gcd([6]) =6, gcd([18]) =18이므로 출력은 4가 됩니다. gcd([4,6]) =2, gcd([4,18]) =2, gcd([6,18]) =6, gcd([4,6,18]) =2이므로 모든 숫자는 [ 4,6,18,2], 4개의 숫자가 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

T :=최대 숫자 + 1
nums :=고유한 모든 숫자를 포함하는 새 집합
답변 :=0
범위 1에서 T - 1까지의 x에 대해 수행
- g :=0
- x ~ T - 1 범위의 y에 대해 x씩 각 단계에서 업데이트합니다.
  - y가 숫자이면
    - g :=gcd(g, y)
  - g가 x와 같으면
    - 루프에서 나오다
- g가 x와 같으면
  - ans :=ans + 1
반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

from math import gcd
def solve(nums):
   T = max(nums) + 1
   nums = set(nums)
   ans = 0

   for x in range(1, T):
      g = 0
      for y in range(x, T, x):
         if y in nums:
            g = gcd(g, y)
         if g == x:
            break

      if g == x:
         ans += 1

   return ans

nums = [4,6,18]
print(solve(nums))

입력

[4,6,18]