LeetCode 878. 第 N 个神奇数字（二分查找）

示例 1：
输入：N = 1, A = 2, B = 3
输出：2

示例 2：
输入：N = 4, A = 2, B = 3
输出：6

示例 3：
输入：N = 5, A = 2, B = 4
输出：10

示例 4：
输入：N = 3, A = 6, B = 4
输出：8
 
提示：
1 <= N <= 10^9
2 <= A <= 40000
2 <= B <= 40000

class Solution {
public:
    int lcmab;//最小公倍数
    int nthMagicalNumber(int N, int A, int B) {
        long long lo = 2, hi = 1e15, ans, mid, mod = 1e9+7, num;
        lcmab = A/__gcd(A,B)*B;// 最小公倍数 = A*B/最大公约数(A,B)
        while(lo <= hi) 
        {
            mid = lo+((hi-lo)>>1);
            num = ct(mid,A,B);// mid 包含多少个 神奇数字
            if(num >= N)
            {
                ans = mid;
                hi = mid-1;
            }
            else
                lo = mid+1;
        }
        return ans%mod;
    }
    long long ct(long long n, int A, int B) {
        return n/A + n/B - n/lcmab;
    }
};