题目
一个正整数如果能被 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 <= 109
2 <= a, b <= 4 * 104
思路
经典二分查找题型，具体思路看代码注释
题解
class Solution: def nthMagicalNumber(self, n: int, a: int, b: int) -> int: #a,b=的最小公倍数 #因为后续计算的时候 需要每一个最小公倍数相当于计算了两次 需要剔除 mcm=lcm(a,b) #check 函数 检查这个数是第多少个数 def check(k:int): tmp=0 tmp+=k//a tmp+=k//b tmp-=k//(mcm) return ans #二分查找 l=0 r=n*max(a,b) while l<r: mid=(l+r)>>1 cc=check(mid) if cc<n: l=mid+1 else: #注意此处 如果 cc==n 这个数不一定是 结果 #因为如果 x是答案 x~x+(min(a,b)-1)的数的CC是一样的 r=mid #结果取模 return r%int(1e9+7)
