Question

Your task is to determine the least common multiple of two integers.

You will need to use the Euclidean algorithm for GCD to prevent going above the time limit.

input specification

The first line will contain a single integer NN (1<N<100001

answer must be in c++ language

The following NN lines will each contain a 2 integers aa and bb (1<a,b<1000000001

Answer 1

CODE:

#include <iostream>
using namespace std;

// to find the GCD of two numbers
int gcd(int a, int b){
    // if a divides b perfectly
    if(a%b==0){
        return b;
    }
    // if a can't divide b perfectly
    return gcd(b%a,a);
}

int main()
{
    // input of number of lines
    int n;
    cin>>n;
    
    // iterating for each line
    while(n>0){
        n--;
        
        // input of 2 numbers
        int a,b;
        cin>>a>>b;
        
        // stores the gcd of a and b in r
        int r = gcd(a,b);
        
        // stores the lcm of a and b in lcm
        int lcm = a*b/r;
            
        cout<<lcm<<endl;
    }

    return 0;
}

INPUT:

3                                                         

4 10                                                                                                                                       

5 12                                                                                                                                       

7 10    

OUTPUT:                                                               

20

60

70