Số III xấu xí trong C ++

Giả sử chúng ta phải viết một chương trình để tìm số xấu thứ n. Số xấu là số nguyên dương chia hết cho a hoặc b hoặc c. Vì vậy, ví dụ, nếu n =3 và a =2, b =3 và c =5, thì đầu ra sẽ là 4, vì các số xấu là [2,3,4,5,6,8,9,10] , cái thứ ba là 4.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo một phương thức có tên ok (), điều này sẽ nhận x, a, b, c, điều này sẽ hoạt động như bên dưới -

• quay lại (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)))

• Từ phương thức chính, thực hiện theo các bước sau -

• thấp:=1, cao:=2 * (10 ^ 9)

• trong khi thấp

  • giữa:=low + (cao - thấp) / 2

  • x:=ok (giữa, a, b, c)

  • nếu x> =n thì high:=mid, ngược lại low:=mid + 1

• trả về cao

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

3
2
3
5

Đầu ra

4