难度: Hard
一个正整数如果能被 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
Submission
运行时间: 25 ms
内存: 16.0 MB
class Solution:
def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
const = 10 ** 9 + 7
l = min(a, b)
r = n * min(a, b)
c = lcm(a, b)
while l <= r:
mid = l + (r - l) // 2
cnt = mid // a + mid // b - mid // c
if cnt >= n:
r = mid - 1
else:
l = mid + 1
return (r + 1) % const
Explain
这道题要找出第n个可以被a或b整除的神奇数字。题解使用二分搜索方法，设定搜索区间的左界为min(a, b)（因为这是第一个可能的神奇数字），右界为n * min(a, b)（这是一个保守的上界，理论上第n个神奇数字不会超过这个值）。中点mid在搜索过程中被检查，看通过a或b除以它可以得到多少个神奇数字。这个计数由mid // a + mid // b - mid // lcm(a, b)给出，后者是为了排除重复计数的情况（即同时被a和b整除的情况）。如果这个计数大于或等于n，说明第n个神奇数字小于或等于mid，因此减小右界。否则，增加左界。二分搜索结束后，r+1即是所求的第n个神奇数字。
时间复杂度: O(log(n))
空间复杂度: O(1)
class Solution:
def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
const = 10 ** 9 + 7 # 定义常量以应对大数字的输出
l = min(a, b) # 初始化搜索区间左端点
r = n * min(a, b) # 初始化搜索区间右端点
c = lcm(a, b) # 计算a和b的最小公倍数
while l <= r: # 使用二分搜索找到第n个神奇数字
mid = l + (r - l) // 2 # 计算中点
cnt = mid // a + mid // b - mid // c # 计算mid时有多少个数是神奇的
if cnt >= n: # 如果计算的数目大于或等于n，说明答案在左侧或者就是mid
r = mid - 1
else: # 否则答案在右侧
l = mid + 1
return (r + 1) % const # 返回结果
Explore
直接从min(a, b)开始逐个检查虽然直观，但效率很低，特别是当n很大或a和b的值很大时。二分搜索法可以显著提高效率，因为它每次将搜索区间减半，从而在对数时间复杂度内找到答案。这种方法利用了数学上的性质，可以快速计算在任意数字x之下，有多少个数可以被a或b整除，从而判断第n个神奇数字是更大还是更小，有效地缩小搜索范围。
在计算有多少个神奇数字时，单独计算`mid // a`和`mid // b`会重复计数那些同时被a和b整除的数字。最小公倍数`lcm(a, b)`是同时被a和b整除的最小数，因此`mid // lcm(a, b)`给出了在mid之下，同时被a和b整除的数字数量。为了得到准确的神奇数字数量，需要从总数中减去这部分重复计数的数字。这是根据包容排斥原理，确保每个数字只被计数一次。
设置右界为`n * min(a, b)`是一个保守的估计，它基于假设所有的神奇数字都是最小可能值`min(a, b)`的倍数。这确保了在最坏情况下（即所有神奇数字均为这一最小值的倍数时），搜索区间仍然包含第n个神奇数字。实际上，由于数字可以同时被a和b整除，所以实际的第n个神奇数字通常会小于这个上界。因此，这个值不大可能小于第n个神奇数字，而是提供了一个足够大的范围以确保包含解。
在二分搜索过程中，如果中间的计数`cnt`大于或等于n，我们会减小右界`r`到`mid - 1`。这意味着最后一次`cnt >= n`时的`mid`实际上可能正是我们需要的解，但此时`r`已经被设置为`mid - 1`。因此，搜索结束时，实际的答案应该是`r + 1`。使用`(r + 1) % const`是为了防止结果超过题目规定的模数`10**9 + 7`，保持结果的正确性和范围。