541. Nth Magical Number

HardBinary Search Binary Search on Answer Math

A positive integer is magical if it is divisible by a or by b. Given n, a, and b, return the n-th smallest magical number, modulo 1,000,000,007. Use binary search with inclusion-exclusion counting. Input: 'n, a, b'.

Input: 'n, a, b'.

Output: Integer — the n-th magical number mod 1e9+7.

Examples

Example 1

Input: 4, 2, 3
Output: 6
Explanation: Magical numbers 2,3,4,6: 4th is 6.

Example 2

Input: 1, 2, 3
Output: 2
Explanation: First magical number.

Example 3

Input: 5, 2, 4
Output: 10
Explanation: 5th magical number.

Constraints

1<=n<=10^9
2<=a,b<=4*10^4

Asked by

Amazon Google Meta

Solve this problem in the editor →