পাইথনে a, b, c দিয়ে বিভাজ্য সংখ্যার সিকোয়েন্স থেকে nth টার্ম বের করার প্রোগ্রাম

চারটি সংখ্যা n, a, b, c দেওয়া আছে। a, b বা c যেকোনো একটি দিয়ে বিভাজ্য সংখ্যাগুলো সর্টেড সিকোয়েন্সে রাখলে ০-ইন্ডেক্সড n-তম টার্ম কত হবে সেটি বের করতে হবে।

উদাহরণস্বরূপ, n=8, a=3, b=7, c=9 হলে সিকোয়েন্স: [3,6,7,9,12,14,15,18,21...] → ৮তম টার্ম (০-ইন্ডেক্সড) = ১৮।

সমাধানের পদ্ধতি (বাইনারি সার্চ + ইনক্লুশন-এক্সক্লুশন)

1. যদি min(a,b,c)==1, তবে সব সংখ্যা বিভাজ্য → রিটার্ন n।
2. LCM বের করুন: ab=lcm(a,b), bc=lcm(b,c), ca=lcm(a,c), abc=lcm(ab,c)।
3. বাইনারি সার্চ left=1, right=10^9:
   • mid = (left+right)//2।
   • numterms = mid//a + mid//b + mid//c - mid//ab - mid//bc - mid//ca + mid//abc (ইনক্লুশন-এক্সক্লুশন)।
   • যদি numterms > n: right = mid-1।
   • যদি numterms < n: left = mid+1।
   • অন্যথায়: return mid - min(mid%a, mid%b, mid%c)।

পাইথন কোড উদাহরণ

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