কম্পিউটার

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(b,c) ) - (x/lcm(a,c)) + (x/lcm(a, lcm(b,c)))

  • মূল পদ্ধতি থেকে, অনুসরণ করুন -

  • কম :=1, উচ্চ :=2 * (10^9)

  • যখন কম <উচ্চ -

    • মধ্য :=নিম্ন + (উচ্চ - নিম্ন) / 2

    • x :=ঠিক আছে(মধ্য, ক, বি, গ)

    • যদি x>=n হয়, তাহলে উচ্চ :=মধ্য, অন্যথায় নিম্ন :=মধ্য + 1

  • উচ্চ রিটার্ন

উদাহরণ (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

আউটপুট

4

  1. C++ এ মিতব্যয়ী নম্বর

  2. C++ পেন্টাটোপ নম্বর

  3. C++ এ কুৎসিত সংখ্যা

  4. C++ এ অ্যাডাম নম্বর