关键词: 二分 容斥原理
题意描述
1. (a,b)的神奇数字:能被a或b整除
2. 第N个神奇数字:排序的第N个
思路分析
判断一个数是不是神奇数字是容易的。那么判断区间之间有多少个神奇数字呢?
思考1：神奇数字有哪些种类?
神奇数字集合分布
- 能被a整除
- 能被b整除
- 能同时被a,b整除，即能被
（a,b的最小公倍数）
思考2：如何求得区间之间神奇数字的个数?
思考3: 一个数是否最终结果如何判断？
且
代码实现
class Solution {
public:
const int MOD=1e9+7;
typedef long long LL;
int nthMagicalNumber(int N, int A, int B) {
LL l=1;
LL r = 1e18;
int ab = 1ll * A *B/gcd(A,B); // 最小公倍数
while(l<r){
LL m = (r+l)/2;
LL cnt =0;
cnt+= m/A+m/B-m/ab;
if(cnt>=N) r=m;
else l=m+1;
}
return l%MOD;
}
};
小结
二分查找的主要套路:
- 数据规模大，
是上限
- 数据有序，或者构造后(前缀和，后缀和)有序
- 分段，找分割点
