Robert Eisele
Engineer, Systems Architect and DBA

# Codingame: Divide the factorial

Original Problem

## Goal

Given two integers A and B, you have to find the largest power of A that divides B! with no remainder.
You have to find the largest integer value of X such that A^X divides B! where B! = B × (B-1) × (B-2) × … × 2 × 1.

Input
One line containing A and B, separated by a single space.
Output
A single line containing X, the largest power of A that divides B!
Constraints
2 ≤ AB ≤ 10^7

## 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 corrosponding 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

« Back to problem overview