784. The nth Number Divisible by Either
Two positive integers a and b are given. Write out the positive integers divisible by a
or by b in increasing order, with no repeats. Print the nth of them, counting from 1.
n = 10, a = 2, b = 3 -> 15 2 3 4 6 8 9 10 12 14 15 and so on
n = 1, a = 2, b = 3 -> 2
n = 5, a = 2, b = 4 -> 10 2 4 6 8 10 ... every multiple of 4 is already a multiple of 2
n = 7, a = 3, b = 3 -> 21 the two divisors coincide
## Walking the list is hopeless
n reaches 10^9 and the divisors reach 40000, so the answer reaches 4 * 10^13. Testing one
integer at a time, or even one multiple at a time, is out of reach. Nothing here needs the list,
only its length up to a point.
## Counting with inclusion and exclusion
Among 1 .. x, the multiples of a number x / a, the multiples of b number x / b, and the
ones counted twice are the multiples of BOTH, which are exactly the multiples of
lcm(a, b). So
count(x) = x / a + x / b - x / lcm(a, b)
with integer division throughout. The last term is the one people leave out. With a = 2 and
b = 3, dropping it counts 6, 12, 18 twice each and the answer comes back far too small.
## Why lcm and not a * b
lcm(a, b) = a / gcd(a, b) * b. Using a * b instead is correct only when a and b are
coprime. With a = 2, b = 4 the shared multiples are the multiples of 4, not of 8, and the
count is wrong from the third entry onwards. The test with a = b is the extreme version of
this: lcm(3, 3) = 3, so count(x) = x/3 + x/3 - x/3 = x/3, which is right.
## Why the count is monotone
Each of the three terms is a non-decreasing step function of x, and while the third is
subtracted, the combination still cannot fall: going from x to x + 1 adds one to the total
exactly when x + 1 is divisible by a or by b, and adds nothing otherwise. Never negative.
## Why the answer is divisible by a or b
Search for the smallest x with count(x) >= n. At the stop, count(x) > count(x - 1), and the
count only rises at an integer that is itself divisible by a or by b. So the value returned
really is a member of the list, not a gap between two of them.
## The bounds
lo = 1 and hi = n * min(a, b). The multiples of the smaller divisor alone already supply
n values by then, so the answer cannot be above it.
## The boundary that breaks a careless implementation
Compute lcm as a / gcd(a, b) * b, dividing FIRST. Writing a * b / gcd(a, b) is the same
number mathematically, and at these bounds it is also safe: a and b stop at 40000, so
a * b stops at 1600000000, under the 2147483647 a signed integer held in 32 bits reaches.
Divide first anyway. The product form is one doubling of the divisor limit away from wrapping, and the same line inside a problem with divisors in the millions wraps on the first call. This is a habit worth acquiring where it costs nothing, which is here.
## Relationship with problem 786
786 runs the same kind of counter, a sum of integer divisions evaluated at a guess, and searches for the smallest argument whose count reaches the target. What separates the two is how that count behaves between consecutive arguments.
Here it rises by at most one at a time, and it rises exactly at the integers divisible by a or
by b, which is why the value the search stops on is guaranteed to be a member of the list. In
786 the count jumps by 2 at 25 and by 3 at 125, so a target can be stepped over entirely and the
search has to finish with an equality check before it is allowed to answer. Whether a lower-bound
search needs that final test is decided by this property and nothing else.
## Overflow
n * min(a, b) reaches 4 * 10^13, so the upper bound, the midpoint and the answer are all
64-bit.
The count is the near miss, and it deserves a number rather than a hand wave. count(x) itself
never exceeds n, which is 10^9, but it is assembled as mid / a + mid / b before the last
term is subtracted, and with a = b = 40000 and n = 10^9 that intermediate sum climbs to
1999999998. That is under 2147483647, so a 32-bit count survives these constraints, with
about 147 million to spare and nothing else. Hold the whole expression in the same 64-bit type
as mid and the margin stops mattering.
## Cost
Time O(log(n * min(a, b))). Space O(1).
Constraints - `1 ≤ n ≤ 10^9` - `1 ≤ a, b ≤ 40000`
Input
The first line contains three integers n, a and b.
Output
Print a single integer: the nth smallest positive integer divisible by a or by b.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.