Chương trình tìm số hạng thứ n của một dãy số chia hết cho a, b, c trong Python

Giả sử chúng ta có bốn số n, a, b và c. Chúng ta phải tìm số hạng thứ n (0 được lập chỉ mục) của dãy số đã sắp xếp chia hết cho a, b hoặc c.

Vì vậy, nếu đầu vào là n =8 a =3 b =7 c =9, thì đầu ra sẽ là 18, vì 9 số hạng đầu tiên của dãy là [1, 3, 6, 7, 9, 12, 14 , 15, 18].

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

• nếu giá trị nhỏ nhất của a, b, c bằng 1 thì
  • return n
• ab:=lcm (a, b), bc:=lcm (b, c), ca:=lcm (a, c)
• abc:=lcm (ab, c)
• left:=1, right:=10 ^ 9
• khi left <=right, thực hiện
  • giữa:=(trái + phải) / 2
  • na:=thương số của giữa / a
  • nb:=thương số của giữa / b
  • nc:=thương số của giữa / c
  • nab:=thương số của mid / ab
  • nbc:=thương số của mid / bc
  • nca:=thương số của mid / ca
  • nabc:=thương số của mid / abc
  • số:=na + nb + nc - nab - nbc - nca + nabc
  • nếu numterms> n, thì
    • right:=mid - 1
  • ngược lại khi numterms
  • left:=mid + 1
• nếu không,
  • trả về giữa - tối thiểu của (giữa mod a, giữa mod b, mod giữa c)

Ví dụ (Python)

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

import math
def lcm(a, b):
   return (a * b) // math.gcd(a, b)
class Solution:
   def solve(self, n, a, b, c):
      if min(a, b, c) == 1:
         return n
      ab, bc, ca = lcm(a, b), lcm(b, c), lcm(a, c)
      abc = lcm(ab, c)
      left, right = 1, 10 ** 9
      while left <= right:
         mid = (left + right) // 2
         na = mid // a
         nb = mid // b
         nc = mid // c
         nab = mid // ab
         nbc = mid // bc
         nca = mid // ca
         nabc = mid // abc
         numterms = na + nb + nc - nab - nbc - nca + nabc
         if numterms > n:
            right = mid - 1
         elif numterms < n:
            left = mid + 1
         else:
            return mid - min(mid % a, mid % b, mid % c)
      return -1
ob = Solution()
n = 8
a = 3
b = 7
c = 9
print(ob.solve(n, a, b, c))

Đầu vào

8, 3, 7, 9

Đầu ra

18