c - Find N'th number divisible by a or b -

given 2 numbers a and b, have find nth number divisible by a or b.

input : first line consists of integer t, denoting number of test cases. second line contains 3 integers a, b and n .

output : each test case, print nth number in new line.

constraints : 1≤t≤10^5 1≤a,b≤10^4 1≤n≤10^9

sample input

1 2 3 10 

sample output

15 

explanation numbers divisible by 2 or 3 are: 2,3,4,6,8,9,10,12,14,15 and 10th number is 15.

my code (in c) :

#include<stdio.h>  int main() {     long long int i,a,b,n,j,c=0,small;     scanf("%lld",&i);     while(i--)     {         scanf("%lld%lld%lld",&a,&b,&n);         if(a==b)         {             printf("%lld ",a*n);             return 0;         }         else         {             if(a>b)                 small = b ;             else                 small = ;             for(j=small;1;j++)             {                 if(j%a==0 || j%b==0)                     c++ ;                 if(c==n)                     break ;             }         }         printf("%lld",j);     }     return 0 ; } 

but not time efficient (i.e. takes more 1 sec) on input : 1000 10000 100000000

you using linear search has o(n) time complexity in worst case, hence takes more 1 sec or more. need improve searching time.

you need use binary search find answer. use pie(principle of inclusion-exclusion) calculate how many numbers 1 x divisible either or b. now, in each step of binary search calculate how many numbers divisible either or b. when number equals n, return , print answer. takes o(log n) steps in worst case.

#include<stdio.h> typedef long long ll;  ll gcd(ll a, ll b) {     if (a == 0)         return b;     return gcd(b % a, a); }  ll bs(ll a, ll b, ll n) {     ll high,low,mid,cnt,lcm;     low = 1;     high = 1e18;     lcm = (a * b) / gcd(a, b);      while(low <= high)     {         mid = (low + high) / 2;         cnt = (mid / a) + (mid / b) - (mid / lcm);          if(cnt < n)             low = mid + 1;         if(cnt > n)             high = mid - 1;         if(cnt == n)             break;     }     while(mid % && mid % b)         mid--;     return mid; }  int main() {     ll a,b,n,t;     scanf("%lld",&t);     while(t--)     {         scanf("%lld %lld %lld", &a, &b, &n);         printf("%lld\n", bs(a, b, n));     }     return 0; }