C++의 못생긴 숫자 III

<시간/>

n번째 못생긴 숫자를 찾는 프로그램을 작성해야 한다고 가정합니다. 추한 숫자는 또는 b 또는 c로 나눌 수 있는 양의 정수입니다. 예를 들어, n =3이고 a =2, b =3 및 c =5이면 추한 숫자가 [2,3,4,5,6,8,9,10]이므로 출력은 4가 됩니다. , 세 번째는 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 :=ok(중간, a, b, c)
- 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));
}

입력