PROBLEM LINK:
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;
}
}