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

Problema este o variatie a unei probleme clasice: dandu-se un sir de $N$ numere intregi sa se determine o secventa de suma maxima. Singura modificare este ca in aceasta problema sirul este circular. In prima parte a solutiei nu vom lua in considerare faptul ca sirul este circular. Pentru a rezolva problema pentru un sir normal exista o solutie clasica $O(N)$. Se calculeaza pentru fiecare $i$ secventa de suma maxima care se termina cu elementul $i$: este fie secventa de suma maxima care se termina la elementul $i-1$, la care se adauga elementul $i$, fie doar elementul $i$. O scurta descriere in pseudocod a acestui algoritm:

Problema este o variatie a unei probleme clasice: dandu-se un sir de $N$ numere intregi sa se determine o secventa de suma maxima. Singura
modificare este ca in aceasta problema sirul este circular. In prima parte a solutiei nu vom lua in considerare faptul ca sirul este circular. Pentru a rezolva problema pentru un sir normal exista o solutie clasica $O(N)$. Se calculeaza pentru fiecare $i$ secventa de suma maxima care se termina cu elementul $i$: este fie secventa de suma maxima care se termina la elementul $i-1$, la care se adauga elementul $i$, fie doar elementul $i$. O scurta descriere in pseudocod a acestui algoritm:

== code(c) |
s = smax = 0;

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$