TRAVELJO - Editorial

editorial
,
1

PROBLEM LINK: CodeChef: Practical coding for everyone

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

DIFFICULTY:

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;
}