# 1201. Ugly Number III

Write a program to find the `n`-th ugly number.

Ugly numbers are **positive integers** which are divisible by `a` **or** `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 <= 10^9`
* `1 <= a * b * c <= 10^18`
* It's guaranteed that the result will be in range `[1, 2 * 10^9]`

找第N个只能被a或b或c整除的独立的数。暴力法是不断遍历和比较a *a* a ..., b *b ... 和c* c ...进一步优化O(N)=>二分所有整数范围，对于mid，小于a，b和c个数分别为mid / a, mid/b和mid/c。但它们之间有重复，根据简单的集合论，要去除mid/ab，mid/ac和mid/bc再加上mid/abc。当abc并非互质时，去除mid/ab等还不够，应当以ab（其它乘数同理）的最小公倍数为基础去除。

```cpp
/*
 * @lc app=leetcode id=1201 lang=cpp
 *
 * [1201] Ugly Number III
 */

// @lc code=start
class Solution {
public:
    int nthUglyNumber(int n, long a, long b, long c) {
        long start = 1, end = INT_MAX;
        long ab = lcm(a, b), ac = lcm(a, c), bc = lcm(b, c), abc = lcm(a, bc);
        while (start < end) {
            const long mid = start + (end - start) / 2;
            const long cnt = mid / a + mid / b + mid / c - mid / ab - mid / ac - mid / bc + mid / abc;
            if (cnt < n) start = mid + 1;
            else end = mid;
        } 
        return start;
    }
};
// @lc code=end


```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/binarysearch/er-fen-range/1201.-ugly-number-iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.