CODEWITHSUNDEEP
algorithm
piotrekg2
piotrekg2

Reputation: 1257

Least common multiple modulo some p

Suppose we have to find least common multiple (lcm) of numbers a1 ... an.

To solve this we can use a recursive solution:

lcm(a, b) = (a * b) / gcd(a, b) where gcd(a, b) denotes greates common divisor of a and b

lcm(a1 ... an) = lcm(a1, lcm(a2 ... an))

The question is:

What if we are interested in lcm(a1 ... an) mod p where p is some prime number. lcm(a1 ... an) is too large to be stored in int.

Upvotes: 2

Views: 3898

Answers (1)

BeaumontTaz
BeaumontTaz

Reputation: 273

There have been some previous questions on the topic:

You have two options:

Option 1: The general trend seems to be to that if your values are still too long for unsigned long long ints then you need to work with the prime decomposition of your numbers. Take each number ai and break it into it's prime factors (2r)(3s)(5t)... . All you have to do to get the LCM is to take the largest exponent for each prime factor.

For example, the LCM of 15 and 18 can be done like this:

15 = (20)(31)(51)

18 = (21)(32)(50)

The largest exponent for 2 is 1, the largest exponent for 3 is 2, and the largest exponent for 5 is 1. Therefore, LCM(15,18) = (21)(32)(51) = 2(9)(5) = 90. But, we can perform the modulo in this multiplication step because ab (mod n) = ((a (mod n)) (b (mod n))) mod n. So just mod after each step of multiplication.

Option 2: This one involves finding the GCD of a subset of ai. Save this as g0 and divide all ai that is a multiple of g0 by g0. Find the GCD for another subset of the new ai and save it at g1. Again, divide all ai that is a multiple of g1 by g1. Repeat this until the GCD for all subsets of ai is 1. Then you just multiply all ai and gi under you mod rules. For example:

LCM(15,18,10)

GCD(15,10) = 5 so g0 = 5 and a = (3,18,2).

GCD(3,18) = 3 so g1 = 3 and a = (1,6,2).

GCD(6,2) = 2 so g2 = 2 and a = (1,3,1). At this point, any subset of a will have a GCD of 1 and we are done.

Putting it all back together LCM(15,18,10) = 5(3)(2)(1)(3)(1) = 90

Upvotes: 3

Related Questions