理解
很典型的考察Nth的问题，主要是找到需要二分的对象，此题是找到Nth magic number,二分的对象明显是数的范围；
从题目的限制条件来看，二分的左值为2（min(A,B)),右值为 N*max(A,B) = 1e14
思路
利用二分进行查找，对进行查找的空间，计算存在的magic number的个数；
重点
1、二分左右值的确定
2、查找给定范围内magic number的个数时，使用mid/A + mid/B - mid/((A * B)/__gcd(A, B))；使用到了最大公约数求最小公倍数；
代码
class Solution {
public:
int nthMagicalNumber(int N, int A, int B) {
long mod = 1e9 + 7;
long left = 2;
long right = 1e14;
while(left < right){
long mid = (left + right)/2;
long ret = mid/A + mid/B - mid/lcm(A,B);
if(ret < N){
left = mid + 1;
}else{
right = mid;
}
}
return left % mod;
}
int gcd(int a, int b){
if(a < b){
swap(a, b);
}
if(b == 0){
return a;
}else{
return gcd(b, a%b);
}
}
int lcm(int a, int b){
return a*b/gcd(a, b);
}
};