h2. 'Zero 2':problema/zero2

Fie $E(N) = 1!*2!*...*N!$. Numarul de zerouri terminale in scrierea lui $E(N)$ in baza $B$ este egal cu numarul de ori $E(N)$ se imparte la $B$. Pentru a determinarea puterea la care apare $B$ in $E(N)$ vom descompune numarul $B$ in factori primi $B = p{~1~}^e{~1~}^*p{~2~}^e{~2~}^*...*p{~k~}^e{~k~}^$. Fie $Nr(N, p)$ puterea la care apare numarul prim $p$ in descompunerea in factori primi a lui $E(N)$. Rezultatul va fi $min([Nr(N, p{~1~})/e{~1~}], [Nr(N, p{~2~})/e{~2~}], ..., [Nr(N, p{~k~})/e{~k~}])$. Asadar problema se va reduce la a calcula $Nr(N, p)$ in mod eficient. O prima rezolvare de complexitate $O(N*lg N)$ este de parcurge toate numerele de la $1$ la $N$ si de a determina puterea la care apare $p$ in $x!$ ({$ 1 ≤ x ≤ N$}) folosind formula $[x/p]+[x/p^2^]+[x/p^3^]+...$.

Fie $E(N) = 1!*2!*...*N!$. Numarul de zerouri terminale in scrierea lui $E(N)$ in baza $B$ este egal cu numarul de ori $E(N)$ se imparte la $B$. Pentru a determinarea puterea la care apare $B$ in $E(N)$ vom descompune numarul $B$ in factori primi $B = p{~1~}^e{~1~}^*p{~2~}^e{~2~}^*...*p{~k~}^e{~k~}^$. Fie $Nr(N, p)$ puterea la care apare numarul prim $p$ in descompunerea in factori primi a lui $E(N)$. Rezultatul va fi $min([Nr(N, p{~1~})/e{~1~}], [Nr(N, p{~2~})/e{~2~}], ..., [Nr(N, p{~k~})/e{~k~}])$. Asadar problema se va reduce la a calcula $Nr(N, p)$ in mod eficient. O prima rezolvare de complexitate $O(N*lg N)$ este de parcurge toate numerele de la $1$ la $N$ si de a determina puterea la care apare $p$ in $x!$ ({$1 ≤ x ≤ N$}) folosind formula $[x/p]+[x/p^2^]+[x/p^3^]+...$.

h3. (problema medie, clasa a 9-a)