Evaluate LCM from N numbers modulo 1000000007
I solved the following problem for LCM: Calculate LCM from N numbers modulo 1000000007
My approach:
typedef unsigned long long ull;
const ull mod=1000000007;
ull A[10009];
/*Euclidean GCD*/
ull gcd(ull a,ull b)
{
while( b != 0)
{
ull t = b;
b= a %t;
a = t;
}
return a;
}
ull lcm(ull a, ull b)
{
return (a/gcd(a,b))%mod*(b%mod);
}
ull lcms(int l ,ull * A)
{
int i;
ull result;
result = 1;
for (i = 0; i < l; i++)
result = lcm(result, A[i])%1000000007;
return result;
}
int main()
{
int T;
cin>>T;
while(T--)/*Number of test cases*/
{
int N;
cin>>N;/*How many Numbers in Array*/
for(int i=0;i<N;++i)
{
cin>>A[i];//Input Array
}
cout<<lcms(N,A)%1000000007<<endl;
}
return 0;
}
I am getting the wrong answer when I post my solution. Limitations:
1<=N<=1000
and 1<=A[i]<=10000
I am guessing that I am getting the wrong answer due to an overflow. How can I improve my code?
Thank!
source to share
1000000007
too big for me to take as an example. Let me use 17
for example:
LCMS(10, 9, 8) % 17 =
LCM(10, LCM(9, 8)) % 17 =
LCM(10, 72) % 17 =
360 % 17 =
3
This is what your code does:
LCMS(10, 9, 8) % 17 =
LCM(10, LCM(9, 8) % 17) % 17 =
LCM(10, 72 % 17) % 17 =
LCM(10, 4) % 17 =
40 % 17 =
6
It is not right.
source to share
Just factor your numbers into arrays of primes, compute lcms over those arrays, and then multiply them with the answer again.
the first primes are 2, 3, 5, 7, 11, 13, .. so, for example, 45 = 3 ^ 2 * 5 turns into {0, 2, 1, 0, 0, ...}
and
vector<uul> lcm(vector<uul> a, vector<uul> b) {
vector<uul> res(a.size());
for (size_t i = 0; i < a.size(); ++i) {
res[i] = max(a[i], b[i]);
}
return res;
}
source to share
your approach is wrong as pointed out by johnchen902 .
Here's my approach:
for i=1 to n
a.take i_th number as x
b.reduce(devide) remaining numbers(i+1_th to n_th) by their gcd with x
c.multiply x to ans and take mod of ans
return ans
source to share