请你帮忙设计一个程序，用来找出第 n 个丑数。
丑数是可以被 a 或 b 或 c 整除的 正整数。
示例 1：
输入：n = 3, a = 2, b = 3, c = 5
输出：4
解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。
示例 2：
输入：n = 4, a = 2, b = 3, c = 4
输出：6
解释：丑数序列为 2, 3, 4, 6, 8, 9, 12... 其中第 4 个是 6。
示例 3：
输入：n = 5, a = 2, b = 11, c = 13
输出：10
解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。
示例 4：
输入：n = 1000000000, a = 2, b = 217983653, c = 336916467
输出：1999999984
提示：
1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18
本题结果在 [1, 2 * 10^9] 的范围内
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ugly-number-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：## Intuition
以题目中测试用例为例：
输入：n = 3, a = 2, b = 3, c = 5
输出：4
我们先多写几个看看规律：
```
2, 3, 4, 6, 8, 9, 10 12
14 15 16 18 20 21 22 24 ...
```
实际上很容易想到这就是最小公倍数(LCM)的应用
```
2的倍数有 12 / 2 = 6 个
3的倍数有 12 / 3 = 4 个
4的倍数有 12 ／ 4 = 3 个
```
那么实际上肯定不是 6 + 4 + 3 个丑数， 因为有有可能一个数字既是2的倍数也是4的倍数，这个时候会被重复计算，我们需要减去，最后我们需要加上同时是三个数字LCM倍数的次数。 实际上这是简单的集合知识。
如果还是不太明白，可以尝试自己画一个韦恩图直观感受一下
## Python3 Code
```python3
class Solution:
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
def LCM(x, y) -> int:
gcd = math.gcd(x, y)
return x * y // gcd
lab = LCM(a, b)
lac = LCM(a, c)
lbc = LCM(b, c)
labc = LCM(lab, lbc)
def countUglyNumbers(n):
return n // a + n // b + n // c + n // labc - (n // lab + n // lac + n // lbc)
# Binary Search
l = 0
r = 2 * 10**9
while (r - l > 1):
# won't overflow
mid = (r + l) // 2
if (countUglyNumbers(mid) >= n):
r = mid
else:
l = mid
return r
```
可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制
LeetCode题解黑白圆盘一个圆盘被涂上了黑白二色，两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向?题解：可以用一个相机即可
LeetCode题解深度优先遍历和回溯的关系？深度优先遍历的范围更大还是回溯的范围更大？为什么？题解：我的理解是：dfs是回溯思想的一种体现- 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。- dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。个人拙见。
LeetCode题解盲人买袜子。他们都各自买了两对黑袜和两对白袜，八对袜子的布质、大小完全相同，而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢？题解：暴力破解， 把袜子都拆开 一人一只 哈哈
LeetCode题解白石搭白塔输入黑块和白块的数量，用输入的方块数目建塔，输出最大高度和种数，两种方法至少一层颜色不同才能算不同的方法塔满足下列要求:1. 塔底层块数和高度数值相同，逐层递减1，最高层为12. 每层颜色相同