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

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^]+...$ care a fost prezentata si 'aici':http://infoarena.ro/preoni-2006/runda-4/solutii. Astfel:
$Nr(N, p) = [N/p]+[N/p^2^]+[N/p^3^]+... + [(N-1)/p]+[(N-1)/p^2^]+[(N-1)/p^3^]+... + [1/p]+[1/p^2^]+[1/p^3^]+... =$
$= [N/p]+[(N-1)/p]+...+[1/p] + [N/p^2^]+[(N-1)/p^2^]+...+[1/p^2^] + [N/p^3^]+[(N-1)/p^3^]+...+[1/p^3^] + ...$.
Fie $S(N, p) = [N/p]+[(N-1)/p]+...+[1/p]$. Putem scrie $Nr(N, p) = S(N, p) + S(N, p^2^) + S(N, p^3^) + ...$.
Vom arata in continuare ca se poate calcula $S(N, p)$ in $O(1)$ astfel:
Termenii $[1/p],[2/p]...[(p-1)/p]$ au valoarea $0$
Termenii $[p/p],[(p+1)/p]...[(2*p-1)/p]$ au valoarea $1$
Termenii $[(2*p)/p],[(2*p+1)/p]...[(3*p-1)/p]$ au valoarea $2$
...
Termenii $[(k*p)/p],[(k*p+1)/p]...[((k+1)*p-1)/p]$ au valoarea $k$
Termenii $[((k+1)*p)/p]...[N/p]$ au valoarea $k+1$
Astfel $k = [N/p]-1$ iar $S(N, p) = k*(k+1)/2*p + (k+1)*(N-(k+1)*p+1)$. Putem acum calcula $Nr(N, p)$ in $O(log{~p~} N)$.

h2. 'Puteri':problema/puteri