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
}