题目描述：

请你帮忙设计一个程序，用来找出第 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

二分法。
如果给定一个数字，能否确认快速[O(1)]这个数字有几个丑数？答案是肯定的，给定数字为n，那么a,b,c对于n有多少个丑数呢？我们先求出a,b,c这几个数字，两两组合和三三组合后的最小公倍数。
设定：lcm1 = lcm(a, b), lcm2 = lcm(a, c), lcm3 = (b, c), lcm4 = lcm(a, b, c)
那么丑数个数为 n / a + n / b + n /c – n / lcm4 – (n / lcm1 + n / lcm4) – (n / lcm2 + n / lcm4)

ps：最小公倍数可以通过两数相乘后除以两数的最大公约数得出，最大公约数可以用辗转相除法得出。

现在我们划定一个取值范围的区间，在这个区间内使用二分法查找就可以了。
区间的上界，自然就是 min(min(a, b), c) * n，而区间的下界如果仔细研究的话又会是一个子算法，采用一个简单的方法来求证一个近似解。

因为区间上界hi是 lo * n，下界可能会小于hi的原因是因为lo以外的其他两个数字可能也会产生丑数，又因为另外两个数字都比lo大，所以区间的下界一定不会低于 lo * n / 3，那么我们就确定了取值区间了lo和hi的范围。

接下来通过二分法在取值区间之内搜索，即可得到答案了，但此时的答案可能比最终答案 x 略大，介于x到x + max(max(a,b),c) 之间，使用 x – min(min(x % a, x % b), x %c) 去除这部分多余的数字即可。

代码：

func nthUglyNumber(n int, a int, b int, c int) int {

	hi, me, lo := sort3(a, b, c)
	up := n * lo//上界，可能的最大的数字
	down := n * lo / 3//下界，可能的最小的数字（TODO 待优化）

	//用于去重的4个最小公倍数
	c1 := minCommonMultiple(hi, lo)
	c2 := minCommonMultiple(hi, me)
	c3 := minCommonMultiple(me, lo)
	c4 := minCommonMultiple(c1, me)
	res := nthUglyNumberRe(n, hi, me, lo, c1, c2, c3, c4, up, down)
	return res
}

var preUp = 0

func nthUglyNumberRe(n int, hi int, me int, lo int, c1 int, c2 int, c3 int, c4 int, up int, down int) int {

	uglyNum := getUgly(up, hi, me, lo, c1, c2, c3, c4)
	if uglyNum > n{
		preUp = up - 1
		return nthUglyNumberRe(n, hi, me, lo, c1, c2, c3, c4, (up + down) / 2, down)//数字太大，把up在up和down之间折半
	} else if uglyNum < n{
		//数字太小说明现在的up已经cover不住了，恢复preUp，提升down到目前的up
		down = up + 1
		up = preUp
		return nthUglyNumberRe(n, hi, me, lo, c1, c2, c3, c4, up, down)
	} else {
		//return up
		a, _, _ := sort3(up - up % lo, up - up % me, up - up % hi)
		return a
	}
}

//获取指定数字的丑数个数
func getUgly(n int, hi int, me int, lo int, c1 int, c2 int, c3 int, c4 int) int {
	return n / hi + n / me + n / lo - n / c1 - n / c2 - n / c3 + n / c4
}


//获取两个数字的最小公倍数
func minCommonMultiple(x int, y int) int {
	a, b := x, y
	for{
		tmp := a % b
		if tmp > 0{
			a = b
			b = tmp
		} else {
			return x * y / b
		}
	}
}

func sort3(a int, b int, c int) (int, int, int) {
	max := 0
	medium := 0
	min := 0
	if a > b{
		if a > c{
			max = a
			if b > c{
				medium, min = b, c
			} else {
				medium, min = c, b
			}
		} else {
			max = c
			if a > b{
				medium, min = a, b
			} else {
				medium, min = b, a
			}
		}
	} else {
		if b > c{
			max = b
			if a > c{
				medium, min = a, c
			} else {
				medium, min = c, a
			}
		} else {
			max = c
			if a > b{
				medium, min = a, b
			} else {
				medium, min = b, a
			}
		}
	}
	return max, medium, min
}