Help me in solving FLOW016 problem

help
,
1

My issue

My code

#include <stdio.h>

int main(void) {
	// your code goes here
	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?

2

@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

3

okay, understood

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

4

@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) {
// your code goes here
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