पायथन में ए, बी, सी द्वारा विभाज्य अनुक्रम के nth टर्म को खोजने का कार्यक्रम

मान लीजिए हमारे पास चार नंबर n, a, b और c हैं। हमें a, b या c से विभाज्य संख्याओं के क्रमबद्ध क्रम का nवां (0 अनुक्रमित) पद ज्ञात करना है।

इसलिए, यदि इनपुट n =8 a =3 b =7 c =9 जैसा है, तो आउटपुट 18 होगा, क्योंकि अनुक्रम के पहले 9 पद हैं [1, 3, 6, 7, 9, 12, 14 , 15, 18].

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

यदि न्यूनतम a, b, c 1 के समान है, तो
- वापसी n
ab :=lcm(a, b), bc :=lcm(b, c), ca :=lcm(a, c)
abc :=lcm(ab, c)
बाएं:=1, दाएं:=10^9
बाएं <=दाएं, करें
- मध्य :=(बाएं + दाएं) / 2
- na :=मध्य / a का भागफल
- nb :=मध्य / b का भागफल
- nc :=मध्य / c का भागफल
- nab :=मध्य / ab का भागफल
- nbc :=मध्य / ईसा पूर्व का भागफल
- nca :=मध्य / ca का भागफल
- nabc :=मध्य / abc का भागफल
- अंक:=ना + एनबी + एनसी - एनएबी - एनबीसी - एनसीए + एनएबीसी
- यदि अंक> n, तो
  - दाएं:=मध्य -1
- अन्यथा जब अंक
- बाएं:=मध्य + 1
अन्यथा,
- मध्य-न्यूनतम (मध्य मोड ए, मिड मॉड बी, मिड मॉड सी) पर लौटें

वापसी -1

उदाहरण (पायथन)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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

इनपुट

8, 3, 7, 9