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)
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.