leetcode 878 第 N 个神奇数字

关键词: 二分 容斥原理

题意描述

1. (a,b)的神奇数字:能被a或b整除
2. 第N个神奇数字:排序的第N个

思路分析

判断一个数是不是神奇数字是容易的。那么判断区间之间有多少个神奇数字呢?

思考1：神奇数字有哪些种类?

神奇数字集合分布

1. 能被a整除
2. 能被b整除
3. 能同时被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;
    }
};

小结

二分查找的主要套路:

• 数据规模大，是上限
• 数据有序，或者构造后(前缀和，后缀和)有序
• 分段，找分割点