LCM of n numbers modulo 10^9+7

general
, , ,
1

Problem link: http://www.codechef.com/JULY14/problems/SGARDEN/

We all know that LCM of more than 2 numbers follows this property:

LCM(a,b,c)=LCM(a,LCM(b,c)) (can be proved easily : Useful link)

Now to find the LCM we can use LCM(a,b)* GCD(a,b)=a*b


I first tried to find the LCM of numbers using this and simply taking modulo at each step.

The problem with this method:


LCM(a,b,c)%mod = LCM(a,LCM(b,c))%mod. (This is a correct relation.)

What I was doing at each step:

LCM(a,LCM(b,c)%mod)%mod, this is wrong because

LCM(a,LCM(b,c)%mod)%mod != LCM(a,b,c)%mod (This was responsible for WA, I was assuming that these 2 values are equal)


Reference: http://stackoverflow.com/questions/16633449/calculate-lcm-of-n-numbers-modulo-1000000007




I guess this would have caused a lot of WA’s for a lot of users.

Then I tried to find the LCM using factorization and got AC using factorization.

11 Likes
2

I used factorization to compute LCM.

3

and I used Python :smiley:
almost feels like cheating, lol

4 Likes
4

Okay, Python can handle large numbers easily without any overflow problem and we can easily take the modulo at the last step.

5

I used Bigint library for c++ … no worries :-p

6

This question could have also been done with great ease in JAVA, using BigInteger.