Codingame Solution: Divide the factorial

Solution

If we had the prime factors of \(A\) and \(B\), the problem statement would read as follows:

\[A^X | B! \Leftrightarrow (a_1^{p_1} \cdot a_2^{p_2} \cdot ... \cdot a_m^{p_m})^X | (b_1^{q_1} \cdot b_2^{q_2} \cdot ... \cdot b_n^{q_n}) \]

For all prime factors \(a_i\) of \(A\), we are looking for the corresponding number \(q_i\) of \(B\), meaning the count of the factor \(a_i\) in \(B\). In \(B!\) all prime factors in the interval \([2, B]\) are vacuously present, which simplifies the thing a bit. By using the power law for division, we know we can subtract the exponents for all \(a_i=b_i\):

\[\frac{b_i^{q_i}}{(a_i^{p_i})^X} = a_i^{q_i - Xp_i}\]

We constrain the exponent to be \(q_i - Xp_i\geq 0\), for which follows that \(\frac{q_i}{p_i}\geq X\) and hence \(X=\lfloor\frac{q_i}{p_i}\rfloor\). The final result is the smallest of such X quotients.

The remaining question is, how can we get the number of factors of a factorial \(q_i\). The easy solution would be to calculate \(B!\) and counting the factors \(a_i\) by division. Since \(B\) can be pretty large and the factors \(a_i\) are prime, we can use Legendre's formula, which states that for any prime number \(p\) and any integer \(n\), the largest exponent \(\nu_{p}(n)\) of \(p\) that still divides \(n!\) is given by:

\[\nu _{p}(n!)=\sum _{{i=1}}^{{\infty }}\left\lfloor {\frac {n}{p^{i}}}\right\rfloor \]

We don't need to loop to infinity, since the floor function makes all summands zero anyway for all \(p^i>n\). We use Ruby to implement the function, since factoring the number \(A\) is a tedious work:

require 'prime'
a, b = gets.split.map {|x| x.to_i}

puts a.prime_division.map { |a_i, p_i|
  t = 1
  q_i = 0
  q_i+= b / (t*= a_i) while t <= b
  q_i / p_i
}.min