题目
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 <= N <= 10^9
2 <= A <= 40000
2 <= B <= 40000
给出 N A B 三个数字，求出第 N 个神奇数字，神奇数字可以被 A 或者 B 整除。
解题思路
假设神奇数字时 M，则 M 是 A 的第 M / A 个倍数，M 是 B 的第 M / B 个倍数，由于 A、B 存在最小公倍数 LCM ，所以 M 即为 A 和 B 的第 M / A + M / B + M / LCM 个神奇数字。
所以思路即为：
- 先求出最小公倍数 LCM
- 然后二分寻找第 N 个神奇数字，以 M / A + M / B + M / LCM < N 为比较条件
代码实现
Runtime: 8 ms
Memory: 20.8 MB
// 当 N 为 1 时，返回 A B 的较小值
if N == 1 {
return min(A, B)
}
// a b tmp 用于辗转相除求最大公约数
var a = A,b = B,tmp = 0
while (b > 0)
{
tmp = a
a = b
b = tmp % b
}
// 最大公约数为 a，最小公倍数为 lcm
let lcm = A * B / a
// 二分搜索的左右边界
var l = 2,r = Int(1e14)
while (l < r)
{
// 中值 m
let m = (l + r) / 2;
// m / A + m / B - m / lcm 得出的结果为 m 是第几个神奇数字
if m / A + m / B - m / lcm < N
{
l = m + 1
}
else
{
r = m
}
}
return Int(l % Int(1e9 + 7))
