1201. Ugly Number III

Given four integers n, a, b, and c, return the nth ugly number.

Ugly numbers are positive integers that are divisible by a, b, or c.

 

Example 1:

Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.
Example 2:

Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6.
Example 3:

Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.
Example 4:

Input: n = 1000000000, a = 2, b = 217983653, c = 336916467
Output: 1999999984
 

Constraints:

1 <= n, a, b, c <= 109
1 <= a * b * c <= 1018
It is guaranteed that the result will be in range [1, 2 * 109].

这题和之前的题目有点不一样，不是依次生成丑数来解体，这样会超时的。

这题我们需要找出规律。对于数字n来说，有n/a个数字能被a整除。

所以对于任意的n，我们可以求出它被某一个数整除的个数，有了个数之后，我们就大概能知道它是第几个丑数，当然这是只有一个a的情况下。

假设多了一个数字b，我们也可以计算n可以被b整除几次，上述两个和就是它能分别被a和b总共整除的次数。

但是上述的算法其实会多算了一部分，就是a和b的最小公倍数，所以我们需要去掉公倍数的个数。

当多了一个c之后，我们需要再加上abc的最小公倍数，因为在去除的过程中，我们把abc最小公倍数所得的个数全部的去掉了，所以我们需要补回来。

同时，我们这里可以使用二分法不断的来尝试来减少尝试的次数，假设一个值符合条件，那么我们需要找出离它最近的一个被a整除的数字，或者是b，或者是c，因为我们获得的数字很有可能不是一个丑数。

class UglyNumberIII : public Solution {
public:
    void Exec() {
        
    }
    int64_t gcd(int64_t a, int64_t b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
    int nthUglyNumber(int n, int a, int b, int c) {
        int64_t lcmAB = (int64_t(a) * int64_t(b)) / gcd(a, b);
        int64_t lcmBC = (int64_t(b) * int64_t(c)) / gcd(b, c);
        int64_t lcmCA = (int64_t(a) * int64_t(c)) / gcd(a, c);
        int64_t lcmABC = (lcmAB * int64_t(c)) / gcd(lcmAB, c);
        int left = 0, right = 2e9;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int count = mid / a + mid / b + mid / c - mid / lcmAB - mid / lcmBC - mid / lcmCA + mid / lcmABC;
            if (count == n) {
                return std::max(mid - mid % a, std::max(mid - mid % b, mid - mid % c));
            }
            if (count > n) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};