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：= ok(mid,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));
}

输入值

3
2
3
5

输出结果

4