package math;

import java.math.BigInteger;

/**

* Created by gouthamvidyapradhan on 23/03/2019

* A positive integer is magical if it is divisible by either A or B.

*

* Return the N-th magical number. Since the answer may be very large, return it modulo 10^9 + 7.

*

*

*

* Example 1:

*

* Input: N = 1, A = 2, B = 3

* Output: 2

* Example 2:

*

* Input: N = 4, A = 2, B = 3

* Output: 6

* Example 3:

*

* Input: N = 5, A = 2, B = 4

* Output: 10

* Example 4:

*

* Input: N = 3, A = 6, B = 4

* Output: 8

*

*

* Note:

*

* 1 <= N <= 10^9

* 2 <= A <= 40000

* 2 <= B <= 40000

*

* Solution: O(log((2 ^ 64) - 1))

* Lets take example of N = 5, A = 4 and B = 6

* The multiple of A are 4, 8, 12, 16, 20, 24 . . .

* The multiple of B are 6, 12, 18, 24 . . .

*

* Lets take a arbitrary number E = 21 and see if this fits the correct answer

* E / A = 5

* E / B = 3

* This means there are 5 + 3 = 8 numbers which are divisible by either A or B such as

* 4, 6, 8, 12, 12, 16, 18, 20 but we have double counted number 12 so we have to reduce 8 by 1 therefore there are

* 7 numbers. But, 7 is greater than required number N = 5 that means we have to search between 0 and E - 1.

* Thus we can binary search to arrive at the answer.

*

* The number of common multiples such as 12 in the above example can be found by E / LCM(4, 6)

*/

public class NthMagicalNumber {

/**

* Main method

* @param args

*/

public static void main(String[] args) {

System.out.println(new NthMagicalNumber().nthMagicalNumber(3, 2, 4));

}

public int nthMagicalNumber(int N, int A, int B) {

final int CONST = 1000000007;

BigInteger bigInteger = new BigInteger(String.valueOf(A));

long aL = (long)A * B;

long lcm = aL / bigInteger.gcd(new BigInteger(String.valueOf(B))).longValue();

long l = 0, h = Long.MAX_VALUE;

while(l <= h){

long m = l + (h - l) / 2;

int status = check(N, m, A, B, lcm);

if(status == 0){

long modA = m % A;

long modB = m % B;

if(modA == 0 || modB == 0) return (int)(m % CONST);

else if(modA < modB) return (int)((m - modA) % CONST);

else return (int)((m - modB) % CONST);

} else if(status == -1){

l = m + 1;

} else {

h = m - 1;

}

}

return 0;

}

private int check(int N, long num, int A, int B, long lcm){

long sum = (num / A) + (num / B);

long common = num / lcm;

sum -= common;

if(sum == N) return 0;

else if(sum > N) return 1;

else return -1;

}

}