Hi. I received time limit exceeded verdict from this problem. I thin I'm using the best algorithm for checking GCD & LCM. Can anyone check this code and help me please? I'm using recursive GCD.

Does anyone have a better algorithm? Thanks

//Bismillah
#include<iostream>
using namespace std;
#define rep(i,t) for (ll i=0;i<t;i++)
#define MOD 1000000007
typedef long long ll;

ll GCD(ll a,ll b)
{
      return b==0?a:GCD(b,a%b);
}
ll LCM(ll a,ll b)
{
      return ( (a/GCD(a,b))*b );
}

int main()
{
    ios_base::sync_with_stdio(0);

    int t;
    cin>>t;
    while (t--)
    {
      int n;
      cin>>n;
      ll res = 1;
      rep(i,n) //read N pairs
      {
        int a,b;
        cin>>a>>b;
        ll x = 1; 
        for (ll j=0;j<b;j++)    //calculate a^b
            x = (x*a)%MOD;
        res = LCM(x,res)%MOD;
      }
      cout<<res<<endl;      

    } 

    return 0;
}
//Code By Daneshvar Amrollahi

There is a better way to solve this problem in a better time.

Think in a way that you are willing to solve this problem manualy without a computer, what do you do?

I think you mean this:

Breaking the numbers into their prime factors and pick up the the common ones with the higher powers and multiply them with the non common ones?

Do you?

I think this is a way which is manually! :D

Daneshvar Amrollahi said:

I think you mean this:

Breaking the numbers into their prime factors and pick up the the common ones with the higher powers and multiply them with the non common ones?

Do you?

I think this is a way which is manually! :D

Exactly :)