Description

Submission

class Solution {
    using ll = long long;
public:
    int nthUglyNumber(int n, int a, int b, int c) {
        ll left = 1, right = INT_MAX;

        while(left < right) {
            ll mid = left + (right - left) / 2;
            
            if(count(mid, a, b, c) < n) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }

    ll count(ll t, ll a, ll b, ll c) {
        return t / a + t / b + t /c - t / lcm(a, b) - t / lcm(a, c) - t / lcm(b, c) + t / lcm(lcm(a,b),c);
    }
};

// find out the minimum number t, such that in range [1, t], there are exactly n numbers that are divisible by a, b or c