0878. Nth Magical Number

# 878. Nth Magical Number#

## 题目 #

A positive integer is magical if it is divisible by either A or 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
``````

Note:

1. `1 <= N <= 10^9`
2. `2 <= A <= 40000`
3. `2 <= B <= 40000`

## 题目大意 #

1. 1 <= N <= 10^9
2. 2 <= A <= 40000
3. 2 <= B <= 40000

## 解题思路 #

• 给出 3 个数字，a，b，n。要求输出可以整除 a 或者整除 b 的第 n 个数。
• 这一题是第 1201 题的缩水版，代码和解题思路也基本不变，这一题的二分搜索的区间是 `[min(A, B)，N * min(A, B)] = [2, 10 ^ 14]`。其他代码和第 1201 题一致，思路见第 1201 题。

## 代码 #

``````
package leetcode

func nthMagicalNumber(N int, A int, B int) int {
low, high := int64(0), int64(1*1e14)
for low < high {
mid := low + (high-low)>>1
if calNthMagicalCount(mid, int64(A), int64(B)) < int64(N) {
low = mid + 1
} else {
high = mid
}
}
return int(low) % 1000000007
}

func calNthMagicalCount(num, a, b int64) int64 {
ab := a * b / gcd(a, b)
return num/a + num/b - num/ab
}

``````

Apr 8, 2023