878. Nth Magical Number

[namespace-io]

二分法

class Solution {
public:
    int gcd(int a, int b){
        if(a == 0) return b;
        return gcd(b % a, a);
    }
    int nthMagicalNumber(int N, int A, int B) {
        
        long lcm = A * B / gcd(A, B);
        long left = 2;
        long right = 1e14;
        long mod = 1e9+7;
        
        while(left < right){
            long mid = (left + right) / 2;
            if(mid / A + mid / B - mid / lcm < N) left = mid + 1;
            else right = mid;
        }
        
        return left % mod;
    }
};