UVA 10680 - LCM

http://uva.onlinejudge.org/external/106/10680.html

This problem ask you to calculate the last non-zero digit of the \(LCM(1...n)\), where \(n\) is between 1 <= n <= 10^6.

The LCM of two integers \(a\) and \(b\)  is the smallest positive integer that is a multiple of both \(a\) and \(b\).

$$\operatorname{lcm}(a,b)=\frac{|a\cdot b|}{\operatorname{gcd}(a,b)}$$

Another way to define the LCM between two integers \(a\) and \(b\) is from their respective standard prime factorization. For each prime factor of \(a\) and \(b\) we take the maximum exponent.

$$\operatorname{lcm}(a,b) = \prod_p p^{\max(a_p, b_p)}$$

I solved this problem using the second definition of LCM. The idea is simple if we want to calculate the LCM for the numbers of \(1, 2, 3, \cdots, n\) we first list all the prime factors between \([1, n]\). For each factor in that list we need the maximum exponent such that \(p^{x} \leq n\). In other words, let's say that \(n = 20\) we want to know the highest power of 2 in the \(LCM(1, 2, \cdots, 20)\) we can try the following:

\(2^{1} \leq 20\) (true)

\(2^{2} \leq 20\) (true)

\(2^{3} \leq 20\) (true)

\(2^{4} \leq 20\) (true)

\(2^{5} \leq 20\) (false)

So the largest power of 2 in the \(LCM(1, 2, \cdots, 20)\) is \(2^{4}\).

 

We repeat this process for the other prime factor in the range \([1,n]\). After that for each prime factor we calculate the answer mod 10. To avoid getting 0's at the end we subtract the \(cnt2 - cnt5\), because between \(1, 2, 3, \cdots, n\) always there is going to be more factors of two than factors of five, this subtraction is always going to be greater than 0. In addition, To speed-up the algorithm the prime factors are pre-calculated using Sieve of Eratosthenes.