Statement▼
Given three integers n
, a
, and b
, return the n
th
magical number.
A magical number is defined as a positive integer that is divisible by either a
or b
.
As the result may be very large, return it modulo
Constraints:
1≤ n
≤109 2≤ a
,b
≤4×104
Solution
To find the n
th
number divisible by either a
or b
, we observe that magical numbers form a sorted sequence of all multiples of a
and b
. Instead of generating this sequence explicitly, we can efficiently count how many magical numbers are
Count of numbers divisible by
a
:⌊x/a⌋ Count of numbers divisible by
b
:⌊x/b⌋ Subtract numbers divisible by both (i.e.,
⌊x/lcm(a,b)⌋ ) to avoid double counting.
Where the least common multiple (LCM) of two numbers,