374. Nth Charmed Number
In a village, a positive whole number is called charmed if it is a multiple of a or a multiple of b (or both). The charmed numbers in increasing order are the lucky sequence of the village, and the elders ask for its n-th member.
Given n, a and b, return the n-th charmed number. Because the answer can be huge, return it modulo 1000000007. Counting up one number at a time is too slow for n up to a billion; find the answer with binary search and the inclusion-exclusion principle.
Example 1
- Input:
- n = 4, a = 3, b = 5
- Output:
- 9
- Explanation:
The charmed numbers are 3, 5, 6, 9, 10, ... so the 4th one is 9.
Example 2
- Input:
- n = 2, a = 6, b = 4
- Output:
- 6
- Explanation:
The charmed numbers are 4, 6, 8, 12, ... so the 2nd one is 6.
Constraints
1 ≤ n ≤ 109
2 ≤ a, b ≤ 4 * 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log(n * min(a, b)))
- Space
- O(1)