package leetcode

func nthUglyNumber(n int, a int, b int, c int) int {
	low, high := int64(0), int64(2*1e9)
	for low < high {
		mid := low + (high-low)>>1
		if calNthCount(mid, int64(a), int64(b), int64(c)) < int64(n) {
			low = mid + 1
		} else {
			high = mid
		}
	}
	return int(low)
}

func calNthCount(num, a, b, c int64) int64 {
	ab, bc, ac := a*b/gcd(a, b), b*c/gcd(b, c), a*c/gcd(a, c)
	abc := a * bc / gcd(a, bc)
	return num/a + num/b + num/c - num/ab - num/bc - num/ac + num/abc
}

func gcd(a, b int64) int64 {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}