C++二分查找算法的应用：第 N 个神奇数字

int GCD(int n1, int n2)
{
int t1 = min(n1, n2);
int t2 = max(n1, n2);
if (0 == t1)
{
return t2;
}
return GCD(t2 % t1, t1);
}
class Solution {
public:
int nthMagicalNumber(int n, int a, int b) {
long long left = -1, right = max(a, b) * (long long)n ;
while (right - left > 1)
{
const auto mid = left + (right - left) / 2;
const long long llNum = mid / a + mid / b - mid /( a * b/GCD(a,b));
if( llNum >= n )
{
right = mid;
}
else
{
left = mid;
}
}
return right%(100010001000+7);
}
};

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
vector<vector> grid;
int res = 0;
{
Solution slu;
res = slu.nthMagicalNumber(5, 2, 4);
Assert(10, res);
}
{
Solution slu;
res = slu.nthMagicalNumber(3, 4, 1000);
Assert(12, res);
}
{
Solution slu;
res = slu.nthMagicalNumber(4, 2, 3);
Assert(6, res);
}

class Solution {
public:
int nthMagicalNumber(int n, int a, int b) {
long long left = 0, right = max(a, b) * (long long)n+1 ;
while (right - left > 1)
{
const auto mid = left + (right - left) / 2;
const long long llNum = mid / a + mid / b - mid /( a * b/GCD(a,b));
if( llNum <= n )
{
left = mid;
}
else
{
right = mid;
}
}
left = max(left - left % a, left - left % b);
return left %(100010001000+7);
}
};

class Solution {
public:
int nthMagicalNumber(int n, int a, int b) {
const int iComMul = ab/GCD(a, b);
long long left = -1, right = max(a, b)(long long)n;
while (right > left + 1)
{
auto llMid = left + (right - left) / 2;
long long llNum = llMid / a + llMid / b - llMid / iComMul;
if (llNum >= n)
{
right = llMid;
}
else
{
left = llMid;
}
}
return right % (1000 * 1000 * 1000 + 7);
}
};