力扣(LeetCode)878. 第 N 个神奇数字(C++)

二分查找+数论

数论知识——辗转相除法、容斥原理。
辗转相除求最大公约数，两数相乘除以最大公约数，就是最小公倍数。
容斥原理求最多不重复元素，最大不重复面积。
<小学数奥>
从数据范围里，用容斥原理找 $a/b$ 的倍数个数，二分查找，改变数据范围，直到数据范围里 $a/b$ 的倍数个数等于 $n$ ，找到答案。

class Solution {
private:
    typedef long long LL;
public:
    int gcd(int a,int b){
        return b?gcd(b,a%b):a;
    }
    LL get(LL m,int a,int b,int c){
        return m/a+m/b-m/c;
    }
    int nthMagicalNumber(int n, int a, int b) {
        const int mod = 1e9+7;
        LL l = 1,r = (LL)n*max(a,b);
        int c = a * b /gcd(a,b);
        while(l<=r){
            LL mid = l + r>>1;
            if(get(mid,a,b,c)<n) l = mid + 1;
            else r = mid - 1;
        }
        return l % mod;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1. 时间复杂度 : $O(log(n\times ma{x}^2(a,b))$ ， 二分查找的时间复杂度 $O(lo{g}_2(n\times max(a,b))$ ， 辗转相除的时间复杂度 $O(log(max(a,b))$ ， 二分查找和辗转相除的 $log$ 底数不同。总时间复杂度 $O(lo{g}_2(n\times max(a,b))+log(max(a,b)$ ， 忽略常数时间复杂度 $O(log(n\times ma{x}^2(a,b))$。
2. 空间复杂度 : $O(1)$ ， 除若干变量使用的常量级空间，没有使用额外的线性空间。

博主致语

理解思路很重要！
欢迎读者在评论区留言，答主看到就会回复的。

AC