โปรแกรมหาพจน์ที่ n ของลำดับที่หารด้วย a, b, c ใน Python . ลงตัว

สมมติว่าเรามีตัวเลขสี่ตัว n, a, b และ c เราต้องหาเทอมที่ n (0 ที่จัดทำดัชนี) ของลำดับการเรียงลำดับของตัวเลขที่หารด้วย a, b หรือ c ได้

ดังนั้น หากอินพุตเป็น 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 :=ผลหารของ mid / a
  • nb :=ผลหารของ mid / b
  • nc :=ผลหารของกลาง / c
  • nab :=ผลหารของ mid / ab
  • nbc :=ผลหารของ mid / bc
  • nca :=ผลหารของ mid / ca
  • nabc :=ผลหารของ mid / abc
  • numterms :=na + nb + nc - nab - nbc - nca + nabc
  • ถ้า numterms> n แล้ว
    • ขวา :=กลาง - 1
  • มิฉะนั้น เมื่อ numterms
  • ซ้าย :=กลาง + 1
• มิฉะนั้น
  • คืนค่ากลาง - ต่ำสุดของ (กลาง mod a, mid mod b, mid mod c)

ตัวอย่าง (Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

ผลลัพธ์

18