class Solution {
public:
int nthMagicalNumber(int n, int a, int b) {
}
};
878. 第 N 个神奇数字
一个正整数如果能被 a 或 b 整除，那么它是神奇的。
给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。
示例 1：
输入：n = 1, a = 2, b = 3 输出：2
示例 2：
输入：n = 4, a = 2, b = 3 输出：6
提示：
1 <= n <= 1092 <= a, b <= 4 * 104
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2022-11-22 09:37:24
const mod int = 1e9 + 7
func nthMagicalNumber(n, a, b int) int {
c := a / gcd(a, b) * b
m := c/a + c/b - 1
r := n % m
res := c * (n / m) % mod
if r == 0 {
return res
}
addA := a
addB := b
for i := 0; i < r-1; i++ {
if addA < addB {
addA += a
} else {
addB += b
}
}
return (res + min(addA, addB)%mod) % mod
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
python3 解法, 执行用时: 52 ms, 内存消耗: 15 MB, 提交时间: 2022-11-22 09:33:28
class Solution:
def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
MOD = 10 ** 9 + 7
c = math.lcm(a, b)
m = c // a + c // b - 1
r = n % m
res = c * (n // m) % MOD
if r == 0:
return res
addA = a
addB = b
for _ in range(r - 1):
if addA < addB:
addA += a
else:
addB += b
return (res + min(addA, addB) % MOD) % MOD
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-11-22 09:32:17
const mod int = 1e9 + 7
func nthMagicalNumber(n, a, b int) int {
l := min(a, b)
r := n * min(a, b)
c := a / gcd(a, b) * b
for l <= r {
mid := (l + r) / 2
cnt := mid/a + mid/b - mid/c
if cnt >= n {
r = mid - 1
} else {
l = mid + 1
}
}
return (r + 1) % mod
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func gcd(a, b int) int {
if b != 0 {
return gcd(b, a%b)
}
return a
}
python3 解法, 执行用时: 32 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-22 09:31:49
class Solution:
def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
'''
容斥原理+二分查找
f(x) = x//a + x//b + x//c c为最小公倍数, f(x): 小于等于x的神奇数字个数
'''
MOD = 10 ** 9 + 7
l = min(a, b)
r = n * min(a, b)
c = math.lcm(a, b) # 最小公倍数
while l <= r:
mid = (l + r) // 2
cnt = mid // a + mid // b - mid // c
if cnt >= n:
r = mid - 1
else:
l = mid + 1
return (r + 1) % MOD