CIRCUIT-Editorial

PROBLEM LINK:

Practice
Contest

Author: Rajendra Prajapat
Tester: Amitabh Paliwal
Editorialist: Rajendra Prajapat, Amitabh Paliwal

DIFFICULTY:

EASY

PREREQUISITES:

gcd, lcm

PROBLEM:

Given that wires w1, w2, w3 . . . wn stops working momentarily after t1,t2,t3. . .tn. find the time at which all wires stops together.

QUICK EXPLANATION:

The L.C.M. of the values gives us the minimum time at which all the wires stop working simultaneously.

EXPLANATION:

To find the L.C.M. we use the relation lcm = num1*num2/gcd(num1, num2), however, this formula only works for two numbers, So will find L.C.M for a given array.
Because L.C.M could be very large so, will find it with modulo 109 + 7.

SOLUTIONS:

Setter's Solution
#include<iostream>
using namespace std;
typedef unsigned long long ull;
ull mod = 1000000007;
unsigned long long gcd(unsigned long long a,unsigned long long b)
{
        if (b == 0) 
                return a; 
        return gcd(b, a % b);
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);       
  int t;
  cin>>t;
  while(t--)
  {
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
   //find lcm of array
    ull ans = 1;
    for(int i=0;i<n;i++)
    {
        ull x = ans%mod;
        ull y ;
        if(arr[i]>x)
        {
                y = arr[i]/gcd(arr[i],x);
                y = ((y%mod)*(x%mod))%mod;
        }
        else
        {
                y = x/gcd(arr[i],x);
                y = (y%mod)*(arr[i]%mod)%mod;
        }
        ans = y%mod;
   }
   cout<<ans<<endl;
  }
}