題目
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 三個(gè)數(shù)字，求出第 N 個(gè)神奇數(shù)字汁咏，神奇數(shù)字可以被 A 或者 B 整除亚斋。
解題思路
假設(shè)神奇數(shù)字時(shí) M，則 M 是 A 的第 M / A 個(gè)倍數(shù)攘滩，M 是 B 的第 M / B 個(gè)倍數(shù)帅刊，由于 A、B 存在最小公倍數(shù) LCM 漂问，所以 M 即為 A 和 B 的第 M / A + M / B + M / LCM 個(gè)神奇數(shù)字赖瞒。
所以思路即為：
- 先求出最小公倍數(shù) LCM
- 然后二分尋找第 N 個(gè)神奇數(shù)字，以 M / A + M / B + M / LCM < N 為比較條件
代碼實(shí)現(xiàn)
Runtime: 8 ms
Memory: 20.8 MB
// 當(dāng) N 為 1 時(shí)蚤假，返回 A B 的較小值
if N == 1 {
return min(A, B)
}
// a b tmp 用于輾轉(zhuǎn)相除求最大公約數(shù)
var a = A,b = B,tmp = 0
while (b > 0)
{
tmp = a
a = b
b = tmp % b
}
// 最大公約數(shù)為 a栏饮，最小公倍數(shù)為 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 得出的結(jié)果為 m 是第幾個(gè)神奇數(shù)字
if m / A + m / B - m / lcm < N
{
l = m + 1
}
else
{
r = m
}
}
return Int(l % Int(1e9 + 7))
