2021-12-11
878. Nth Magical Number

Topic: Math, Binary Search
Difficulty: Hard

Problem:
A positive integer is magical if it is divisible by either a or b.

Given the three integers n, a, and b, return the n^th magical number. Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: n = 1, a = 2, b = 3
Output: 2

Example 2:

Input: n = 4, a = 2, b = 3
Output: 6

Example 3:

Input: n = 5, a = 2, b = 4
Output: 10

Example 4:

Input: n = 3, a = 6, b = 4
Output: 8

Constraints:

1 <= n <= 10^92 <= a, b <= 4 * 10^4