Help me in solving FLOW016 problem

My code

``````#include <stdio.h>

int main(void) {
int t;
scanf("%d",&t);
while(t--)
{
int a,b;
scanf("%d %d",&a,&b);
int gcd,lcm;
for(int i=1; i<=(a<b?a:b);i++)
{
if(((a%i)==0) && ((b%i)==0))
gcd=i;
}
lcm=(long int)(a*b)/gcd;
printf("%d %li\n",gcd,lcm);
}
return 0;
}

``````

Problem Link: FLOW016 Problem - CodeChef

What’s wrong in this code?

@sagunsingh
use long long int in all but this is also not correct since it will give tle
so to remove tle u have to find gcd in log(n) time complexity which can be done by using euclidean algorithm

okay, understood

however, instead of tle, it is showing that the answer is wrong

@sagunsingh
here is the code for reference
include <stdio.h>
long long int Gcd(long long int a,long long int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;

``````// Base case
if (a == b)
return a;

// a is greater
if (a > b)
return Gcd(a - b, b);
return Gcd(a, b - a);
``````

}
int main(void) {
int t;
scanf(“%d”,&t);
while(t–)
{
long long int a,b;
scanf(“%lli %lli”,&a,&b);
long long int gcd,lcm;
gcd=Gcd(a,b);
lcm=(a*b)/gcd;
printf(“%lli %lli\n”,gcd,lcm);
}
return 0;
}

1 Like