Imediat rezulta:

A = T1^(R1 * Q) * ... * TK^(RK * Q)

$A = T{~1~}^R1 * Q^ * ... * T{~K~}^RK * Q^$

Al doilea pas este sa observam ca daca aflam pentru fiecare T[i],B[i] astfel incat B[i]! se divide la Ti ^(Ri * Q) atunci B (numarul cautat in problema) este maximul dintre B[i]. Implicatia imediata e ca putem sa ne ocupam de fiecare numar prim in parte fara sa tinem cont de celelalte.

Al doilea pas este sa observam ca daca aflam pentru fiecare $T{~i~}$, $B{~i~}$ astfel incat $B{~i~}!$ se divide la $T{~i~}^Ri * Q^$ atunci $B$ (numarul cautat in problema) este maximul dintre $B{~i~}$. Implicatia imediata e ca putem sa ne ocupam de fiecare numar prim in parte fara sa tinem cont de celelalte.

Al treilea pas consta in determinarea B[i]-urilor cu ajutorul cautarii binare. Pentru o valoare canditata X (din cautarea binara) trebuie sa calculam puterea lui T[i] in descompunerea lui X!. Acest lucru se afla simplu ca fiind [ X / T[i] ] + [ X / (T[i] ^2) ] + ... (unde prin [x] intelegem partea intreaga a lui x). Cautarea binara se poate optimiza observand ca B[i] este intotdeauna divizibil cu T[i], ba mai mult nu va fi mai mare decat (R[i] * Q)*T[i] (observatie necesara obtinerii punctajului maxim). In concluzie, vom cauta binar o valoare intreaga K in intervalul [1, R[i] * Q] astfel incat B[i] = K * T[i] sa aiba propietata ca B[i]! se divide la T[i] ^(Ri * Q) . Va puteti intreba de ce putem cauta binar. Este simplu: daca o valoare X are propietatea ca X! se divide la Y (unde lui X si Y le putem da semnificatiile dorite de noi) atunci, evident, si (X + 1)! se divide la Y.

Al treilea pas consta in determinarea $B{~i~}$-urilor cu ajutorul cautarii binare. Pentru o valoare candidata $X$ (din cautarea binara) trebuie sa calculam puterea lui $T{~i~}$ in descompunerea lui $X!$. Acest lucru se afla simplu ca fiind $[X/T{~i~}] + [X/(T{~i~}^2^)] + ... (unde prin $[x]$ intelegem partea intreaga a lui $x$). Cautarea binara se poate optimiza observand ca $B{~i~}$ este intotdeauna divizibil cu $T{~i~}$, ba mai mult nu va fi mai mare decat $(R{~i~} * Q) * T{~i~}$ (observatie necesara obtinerii punctajului maxim). In concluzie, vom cauta binar o valoare intreaga $K$ in intervalul $[1, R{~i~} * Q]$ astfel incat $B{~i~} = K * T{~i~}$ sa aiba propietata ca $B{~i~}!$ se divide la $T{~i~}^Ri * Q^$. Va puteti intreba de ce putem cauta binar. Este simplu: daca o valoare $X$ are propietatea ca $X!$ se divide la $Y$ (unde lui $X$ si $Y$ le putem da semnificatiile dorite de noi) atunci, evident, si $(X + 1)!$ se divide la $Y$.

Solutia finala va avea complexitatea O(sqrt(P) * log(Q) * log(Q)). Exista o serie de solutii intermediare care permiteau obtinerea de punctaje suficient de mari si de aceea problema a fost considerata medie desi rezolvarea completa este destul de dificila.

Solutia finala va avea complexitatea $O(sqrt(P) * log(Q) * log(Q))$. Exista o serie de solutii intermediare care permiteau obtinerea de punctaje suficient de mari si de aceea problema a fost considerata medie desi rezolvarea completa este destul de dificila.

 
 
Matrix

h2. Matrix

(problema grea clasa a 9-a, problema medie clasa a 10-a)