C++-এ অগ্লি নাম্বার III

মান লিজিয়ে আমাদের n-তম অগ্লি নাম্বার বের করার প্রোগ্রাম লিখতে হবে। অগ্লি নাম্বার হলো সেগুলো পজিটিভ ইন্টিজার যেগুলো a বা b বা c দিয়ে বিভাজ্য। উদাহরণস্বরূপ, যদি n = 3 এবং a = 2, b = 3 এবং c = 5 হয়, তবে আউটপুট হবে 4, কারণ অগ্লি নাম্বার গুলো হলো [2,3,4,5,6,8,9,10], তৃতীয়টি হলো 4।

সমাধানের ধাপসমূহ

ok() নামে একটি মেথড তৈরি করুন, যা x, a, b, c নেবে, এটি নিচের মতো কাজ করবে:
- রিটার্ন (x/a) + (x/b) + (x/c) – (x/lcm(a,b)) - (x/lcm(b, c)) - (x/lcm(a,c)) + (x/lcm(a, lcm(b,c)))
মেইন মেথড থেকে নিচের কাজ করুন:
- low := 1, high := 2 * (10^9)
- while low < high:
  - mid := low + (high - low) / 2
  - x := ok(mid, a, b, c)
  - যদি x >= n হয়, তবে high := mid, অন্যথায় low := mid + 1
- high রিটার্ন করুন

উদাহরণ (C++)

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন -

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    lli gcd(lli a, lli b){
        return b == 0? a: gcd(b, a % b);
    }
    lli lcm(lli a, lli b){
        return a * b / gcd(a, b);
    }
    lli ok(lli x, lli a, lli b, lli c){
        return (x / a) + (x / b) + (x / c) - (x / lcm(a, b)) - (x / lcm(b, c)) - (x / lcm(a, c)) + (x / lcm(a, lcm(b, c)));
    }
    int nthUglyNumber(int n, int a, int b, int c) {
        int low = 1;
        int high = 2 * (int) 1e9;
        while(low < high){
            int mid = low + (high - low) / 2;
            int x = ok(mid, a, b, c);
            if(x >= n){
                high = mid;
            }
            else low = mid + 1;
        }
        return high;
    }
};

main(){
    Solution ob;
    cout << (ob.nthUglyNumber(3,2,3,5));
}

ইনপুট

3 2 3 5