878. Nth Magical Number

Link

Solution

關鍵在於如何找出num以下有多少Magical Number

f(num) = num/A + num/B - num/lcm(A,B)

知道這點之後就是一般的binary search問題，找出滿足條件的最小num

 long lcm;
    public int nthMagicalNumber(int N, int A, int B) {
         if(B > A){
            int temp = A;
            A = B;
            B = temp;
        }
        long min = B;
        long max = (long)A*N;
        lcm = A*B/gcd(A,B);
        
        
        while(min < max){
            
            long mid = min + (max-min)/2;
            
            if(isEnough(mid, N, A, B)){
                max = mid;
            }
            else{
                min = mid+1;
            }
        }
        
        return (int)(min%(1e9 + 7));
    }
    
    
    public long gcd(int A, int B){
       
        if(B == 0) return (long)A;
        
        return gcd(B, A%B);
        
    }
    
    
    
    
    public boolean isEnough(long num, int N, int A, int B){
        
        long total = num/A + num/B - num/lcm;
        if(total >= (long)N) return true;    
        return false;
    }