Chương trình tìm số lượng các chuỗi con khác nhau GCD trong Python

Giả sử chúng ta có một số mảng có giá trị dương. Chúng ta phải tìm số lượng GCD khác nhau trong số tất cả các dãy con không rỗng của nums. Như chúng ta biết GCD của một dãy số là giá trị lớn nhất chia đều tất cả các số trong dãy.

Vì vậy, nếu đầu vào giống như nums =[4,6,18], thì đầu ra sẽ là 4 vì gcd ([4]) =4, gcd ([6]) =6, gcd ([18]) =18 gcd ([4,6]) =2, gcd ([4,18]) =2, gcd ([6,18]) =6, gcd ([4,6,18]) =2 nên tất cả các số là [ 4,6,18,2], có 4 số.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• T:=tối đa nums + 1

• nums:=một tập hợp mới chứa tất cả các số nums riêng biệt

• ans:=0

• đối với x trong phạm vi từ 1 đến T - 1, thực hiện

  • g:=0

  • đối với y trong phạm vi x đến T - 1, cập nhật từng bước x, thực hiện

    • nếu y bằng nums thì

      • g:=gcd (g, y)

    • nếu g giống với x thì

      • đi ra từ các vòng lặp

  • nếu g giống với x thì

    • ans:=ans + 1

• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn

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))

Đầu vào

[4,6,18]

Đầu ra

4