In this HackerEarthNumbers II problem solution, we have given two numbers a and b, you have to find the Nth number which is divisible by a or b.


HackerEarth Numbers II problem solution


HackerEarth Numbers II problem solution.

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include<stdio.h>

#define mod 1000000007
#define ll long long
#define nax 100005

using namespace std;


long long findTerm(long long a,long long b,long long lcm,long long value)
{

return (value/a) + (value/b) - (value/lcm);
}


long long solve(long long a,long long b , long long N)
{


long long low = 1;
long long high = 100000000000000000LL;
long long gcd = __gcd(a,b);
long long lcm = (a*b)/gcd;
long long ans;
while(low<=high)
{
long long mid = (low+high)/2;
long long term=findTerm(a,b,lcm,mid);
if(term>=N)
{

ans = mid;
high = mid-1;
}
else
low=mid+1;




}
return ans;



}

int main()
{


int t;
long long a,b,N;
cin>>t;
while(t--)
{

cin>>a>>b>>N;
cout<<solve(a,b,N)<<"\n";
}




}

Second solution

#include<bits/stdc++.h>
#define inf 1e18
#define ll long long
using namespace std;
ll a,b,n,l;
ll gcd(ll x,ll y)
{
if(y==0)return x;
else return gcd(y,x%y);
}
bool f(ll x)
{
ll val= x/a + x/b - x/l;
if(val>=n)return 1;
return 0;
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>a>>b;
cin>>n;
ll low=min(a,b),high=inf;
ll ans;
l=(a*b)/gcd(a,b);
while(low<=high)
{
ll mid=(low+high)/2;
if(f(mid))
{
ans=mid;
high=mid-1;
}
else
low=mid+1;
}
cout<<ans<<"\n";
}
}