Editorial for COCI '20 Contest 4 #2 Vepar

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

For simplicity, replace the expression

$\displaystyle a \times (a+1) \times \dots \times b \mid c \times (c+1) \times \dots \times d$ $a \times (a + 1) \times \dots \times b ∣ c \times (c + 1) \times \dots \times d$

with the equivalent

$\displaystyle (c-1)! \times b! \mid (a-1)! \times d!$ $(c - 1)! \times b! ∣ (a - 1)! \times d!$

For each prime $p$ $p$ , define the map $v_p(x)$ $v_{p} (x)$ which returns the largest power of $p$ $p$ which divides $x$ $x$ .

The left-hand side divides the right-hand side if an only if: for each $p$ $p$ , we have $v_p$ $v_{p}$ of the left-hand side is at most the $v_p$ $v_{p}$ of the right-hand side.

It's easy to see $v_p(xy) = v_p(x)+v_p(y)$ $v_{p} (x y) = v_{p} (x) + v_{p} (y)$ . We now want only $v_p(x!)$ $v_{p} (x!)$ .

Proposition: We have

$\displaystyle v_p(x!) = \left\lfloor \frac{x}{p} \right\rfloor + \left\lfloor \frac{x}{p^2} \right\rfloor + \left\lfloor \frac{x}{p^3} \right\rfloor + \dots$ $v_{p} (x!) = ⌊ \frac{x}{p} ⌋ + ⌊ \frac{x}{p^{2}} ⌋ + ⌊ \frac{x}{p^{3}} ⌋ + \dots$

Proof: The first summand counts multiples of $p$ $p$ , the second counts multiples of $p^2$ $p^{2}$ , and so on.

The solution is thus: find all primes up to $10^7$ $10^{7}$ , implement $v_p(x!)$ $v_{p} (x!)$ , and check the relevant inequality of $v_p$ $v_{p}$ for each prime.

Comments

There are no comments at the moment.