Số Xấu III Trong C++

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

Để giải quyết, chúng ta làm theo các bước:

• Tạo phương thức ok(x, a, b, c) trả về: (x/a) + (x/b) + (x/c) – (x/lcm(a,b)) - (x/lcm(b,c)) - (x/lcm(a,c)) + (x/lcm(a, lcm(b,c))).

• Từ phương thức chính: low := 1, high := 2 * 10^9.

• Khi low < high:

  • mid := low + (high - low) / 2.

  • x := ok(mid, a, b, c).

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

• Trả về high.

Ví dụ (C++)

Hãy xem 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;
    }
};

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

Đầu vào

3 2 3 5

Đầu ra

4