Ugly Number III

Ugly Number III asks for the nth positive integer divisible by at least one of a, b, or c. The predicate “there are at least n qualifying numbers up to x” is monotone, so binary-search x. Count qualifying values with inclusion-exclusion: x/a + x/b + x/c - x/lcm(a,b) - x/lcm(a,c) - x/lcm(b,c) + x/lcm(a,b,c). Compute each LCM as u/gcd(u,v)*v using a wide integer and cap it above the search bound to avoid overflow. Search from one to a safe upper bound such as n*min(a,b,c) in 64-bit arithmetic, returning the first x with count at least n. Complexity is O(log upperBound * log max(a,b,c)) due to gcd calls, with O(1) space. Test overlapping divisors and equal divisors.