# PROBLEM LINK: CodeChef: Practical coding for everyone

Author: Viknesh R
Tester: John Zakkam
Editorialist: Viknesh R

EASY

# PREREQUISITES:

Math, Binary Search

# PROBLEM:

After defending The Wall from the White Walkers, Jon Snow needs to head back to King’s Landing and Winterfell to avenge his father’s death. Jon Snow has a map in his hand but he realizes that the map is too old to be read. Therefore, Jon Snow comes up with a plan. He calculates a number called N-th Travel Number and using this number, he finds his way to King’s Landing. Help Jon Snow to calculate N-th Travel Number.

A number is said to be a Travel Number if it is divisible by either A or B.

Since the Travel Number can be large, output the number modulo (10^9 + 7).

# EXPLANATION:

Say L=lcm(A,B), the least common multiple of A and B; and let f(x) be the number of magical numbers less than or equal to x. A well known result says that L = \frac{A * B}{\text{gcd}(A, B)}, and that we can calculate the function \gcd.

Then f(x) = \lfloor \frac{x}{A} \rfloor + \lfloor \frac{x}{B} \rfloor - \lfloor \frac{x}{L} \rfloor. Why? There are \lfloor \frac{x}{A} \rfloor numbers A, 2A, 3A, \cdots that are divisible by A, there are \lfloor \frac{x}{B} \rfloor numbers divisible by B, and we need to subtract the \lfloor \frac{x}{L} \rfloor numbers divisible by A and B that we double counted.

Finally, the answer must be between 0 and N * \min(A, B).
Without loss of generality, suppose A \geq B, so that it remains to show

\lfloor \frac{N * \min(A, B)}{A} \rfloor + \lfloor \frac{N * \min(A, B)}{B} \rfloor - \lfloor \frac{N * \min(A, B)}{\text{lcm}(A, B)} \rfloor \geq N

\Leftrightarrow \lfloor \frac{N*A}{A} \rfloor + \lfloor \frac{N*A}{B} \rfloor - \lfloor \frac{N*A*\gcd(A, B)}{A*B} \rfloor \geq N

\Leftrightarrow \lfloor \frac{N*A}{B} \rfloor \geq \lfloor \frac{N*\gcd(A, B)}{B} \rfloor

\Leftrightarrow A \geq \gcd(A, B)

# SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

int gcd(int x, int y)
{
if(x == 0)
{
return y;
}
return gcd(y % x, x);
}

int nth_travel_number(int n, int a, int b)
{
int lcm = a / gcd(a, b) * b;
long int low = 0;
long int high = (long) n * min(a,b);

while(low < high)
{
long mid = low + (high - low) / 2;

if(mid / a + mid / b - mid / lcm < n)
{
low = mid + 1;
}
else
{
high = mid;
}
}
return (int) (low % MOD);
}

int main()
{
int t;
cin >> t;
int n[t], a[t], b[t];

for(int i = 0; i < t; ++i)
{
cin >> n[i] >> a[i] >> b[i];
}

for(int i = 0; i < t; ++i)
{
cout << nth_travel_number(n[i], a[i], b[i]) << endl;
}
return 0;
}