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


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