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^]+...$ care a fost prezentata si 'aici':http://infoarena.ro/preoni-2006/runda-4/solutii. Astfel:

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^] + ...$.

...
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)$.

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)$. Factorizarea numarului $B$ se poate face in $O( &rad; B)$.

h2. 'Puteri':problema/puteri