878. Nth Magical Number

HARD
https://leetcode-cn.com/problems/nth-magical-number/
https://tianchi.aliyun.com/oj/338592228998370026/357527484118536806
A positive integer is magical if it is divisible by either a or b.

Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 109 + 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

Constraints:

1 <= n <= 109
2 <= a, b <= 4 * 104

class Solution {
public:
int nthMagicalNumber(int n, int a, int b) {
int MOD = 1e9 + 7;
int L = a * b / gcd(a, b);
long long lo = 0;
long long hi = (long) 1e15;
while(lo < hi)
{
long long mi = lo + (hi - lo) / 2;
if (mi / a + mi / b - mi / L < n)
lo = mi + 1;
else
hi = mi;
}
return (int)(lo % MOD);
}
};