Spoj CPPLCM01 - LCM & GCD 1 Solution

 Problem Link: https://www.spoj.com/PTIT/problems/CPPLCM01/

Solution in C++: 

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

///**********ALLAH IS ALMIGHTY************///

#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;

ll gcd(ll a, ll b)

{

    if (!a)

        return b;

    return gcd(b % a, a);

}

ll reduceB(ll a, string b)

{

    ll mod = 0;

    for (int i = 0; i <b.size(); i++)

        mod = (mod * 10 + b[i] - '0') % a;

    return mod;

}

ll gcdLarge(ll a, string b)

{

    ll num = reduceB(a, b);

    return gcd(a, num);

}

int main()

{

    long long a,t,lc,gc,r,ans;

    string b;

    cin>>t;

    while(t--)

    {

        cin>>a>>b;

        gc=gcdLarge(a, b);

        stringstream geek(b);

        geek>>r;

        lc=(a*r)/gc;

        cout<<lc<<" "<<gc<<endl;

    }

    return 0;

}