TLE in FLOW016

, ,
1

Can anyone help me to optimize my code. I m getting time limit exceed error.
here is code for Finding GCD and LCM:
#include
using namespace std;

int main() {
// your code goes here

int t;
cin>>t;
while(t--){
long long int a,b;
    cin>>a>>b;
    int divisor;
    //GCD 
    if(a>b)  divisor=b+1;
    else divisor=a+1;
    while(divisor--){
        if(a%divisor==0 && b%divisor==0){
            break;
        }
    }//ends while
    
    //lcm
   long long int lcm;
    lcm=(a*b)/divisor;
  //  cout<<divisor<<" ";
     printf("%ld ", divisor);
      printf("%ld \n", lcm);
   // cout<<lcm<<"\n";
}
return 0;

}

2

use euclidean algorithm it will work in logn time for finding the gcd of two numbers.
and lcm = a*b/gcd(a,b)

1 Like
3 
int gcd(int a,int b){
     if(b==0) return a;
     return gcd(b,a%b);
}
2 Likes
4

thanks @shivam565
I modified my Algorithm by using Euclidean Algorithm and now it’s working fine.
Here is my code which is accepted.

#include
using namespace std;

int main() {
// your code goes here

int t;
cin>>t;
while(t--){
   long long int a,b;
    
    cin>>a>>b;
 long long int aTemp,bTemp;
    aTemp=a;
    bTemp=b;
    int divisor;
    //GCD 
    for(int i=0;i<8;i++){
        
    if(a%b!=0 && b%a!=0){
        
    if(a>b)  a=a%b;
    else b=b%a;
    }//outer if else
    else break;
    }//for loop
  
    
    if(a>b)  divisor=b+1;
    else divisor=a+1;
    while(divisor--){
      
        if(divisor>0 && a%divisor==0 && b%divisor==0){
            break;
        }
    }//ends while
    
    //lcm
   long long int lcm;
    lcm=(aTemp*bTemp)/divisor;
      cout<<divisor<<" ";
      cout<<lcm<<"\n";
   
}
return 0;

}

5

:+1: