# 878 Nth Magical Number

題目給三個正整數：N, A, B Magical Number的定義：可以被A整除或可以被B整除 要找第N個magical number。

• Since the answer may be very large, return it modulo 10^9 + 7

example

Input: N = 4, A = 2, B = 3
Output: 6

Idea 用binary search，上界設成long.MAX_VALUE，下界設成2，每次取mid，看mid是第幾個magical number。 如何看是第幾個magical number: mid/A + mid/B + mid/gcd

Pseudocode

while(lo < hi)
    mid = lo + (hi-lo)/2
    count = mid/A + mid/B + mid/gcd
    if(count >= N) hi = mid
    else lo = mid+1

return lo/(10^9+7)

Code

class Solution {
    public int nthMagicalNumber(int N, int A, int B) {
        long low = 1, high = Long.MAX_VALUE;
        int M = 1000000007;
        while (low < high) {
            long mid = low + (high - low) / 2;
            long count = mid/A + mid/B - mid / (A * B / gcd(A, B));

            if (count >= N) {
                high = mid;
            } else {
                low = mid + 1;
            }

        }
        return (int)(low % M);
    }
    private int gcd(int A, int B) {
        if (A < B) {
            int temp = A;
            A = B;
            B = temp;
        }
        if (A % B == 0) {
            return B;
        } else {
            return gcd(B, A % B);
        }
    }
}

剛剛這個是log(long.MAX_VALUE)的做法，可以再用數學方法逼近O(1)

Idea

example: 5, 2, 3

2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16
gcd(2,3) = 6

6 -> 4th
12 -> 8th
18 -> 12th

可以先找出gcd(A,B)是第n個，進而在N/n和N/n+1的範圍內用binary search找到答案。

ref: https://leetcode.com/problems/nth-magical-number/discuss/154612/Java-Binary-Search-Solution