HackerEarth Supertables problem solution

In this HackerEarth Supertables problem solution, Little Timmy is exceptionally good at math tables, so his maths teacher decided to make things a bit more interesting. His teacher takes two numbers A and B and merges the tables of A and B in sorted order (ascending order), removing the duplicates and thus creates supertable of A and B and asks Little Timmy the Nth number in the supertable.

Given A, B and N, calculate the Nth number in the supertable of A and B.

HackerEarth Supertables problem solution.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
    long long t,a,b,n;
    cin >> t;
    while ( t-- ) {
        cin >> a >> b >> n;
        long long p = __gcd(a,b);
        p = (a*b)/p;
        long long L,R,M;
        L = 1;
        R = 100000000000000000LL;
        long long ans;
        while ( L <= R ) {
            M = (L+R)/2;
            long long val = M/a + M/b - M/p;
            if ( val == n ) {
                ans = max((M/a)*a, (M/b)*b);
                cout << ans << endl;
                break;
            }
            else if ( val < n ) {
                L = M+1;
            }
            else {
                R = M-1;
            }
        }
    }
    return 0;
}

HackerEarth Supertables problem solution.

Leave a Reply