Vi se dau două numere n și k. Găsiți cea mai mare putere a lui k x astfel încât n! să fie divizibil cu \(k^x\).

Pentru k numar prim

Să luăm mai întâi în considerare cazul unui număr prim k. Expresia explicită pentru factorial: \(n! = 1 \cdot 2 \cdot 3 \ldots (n-1) \cdot n\)

Observați că fiecare al k-lea element al produsului este divizibil cu k, adică adaugă +1 la răspuns; numărul acestor elemente este \(\Bigl\lfloor\dfrac{n}{k}\Bigr\rfloor\)

Apoi, fiecare al \(k^2\)-lea element este divizibil cu \(k^2\), adică adaugă încă +1 la răspuns (prima putere a lui k a fost deja numărată în paragraful anterior). Numărul de astfel de elemente este \(\Bigl\lfloor\dfrac{n}{k^2}\Bigr\rfloor\).

Și așa mai departe, pentru fiecare i, fiecare al \(k^i\)-lea element adaugă încă +1 la răspuns, și există \(\Bigl\lfloor\dfrac{n}{k^i}\Bigr\rfloor\) astfel de elemente.

Răspunsul final este: \(\Bigl\lfloor\dfrac{n}{k}\Bigr\rfloor + \Bigl\lfloor\dfrac{n}{k^2}\Bigr\rfloor + \ldots + \Bigl\lfloor\dfrac{n}{k^i}\Bigr\rfloor + \ldots\).

Suma este, bineînțeles, finită, deoarece doar aproximativ primele \(\log_k n\) elementele nu sunt zero. Astfel, timpul de execuție al acestui algoritm este \(O(\log_k n)\).

Implementare

int fact_pow (int n, int k) {
    int res = 0;
    while (n) {
        n /= k;
        res += n;
    }
    return res;
}

Pentru un numar k compus

Aceeași idee nu poate fi aplicată direct. În schimb, se poate calcula un factor k reprezentat ca \(k = k_1^{p_1} \cdot \ldots \cdot k_m^{p_m}\)

Pentru fiecare \(k_i\), găsim numărul de ori de câte ori este prezent în n! folosind algoritmul descris mai sus – să numim această valoare \(a_i\). Răspunsul pentru numarul ka compus va fi:

\(\min_ {i=1 \ldots m} \dfrac{a_i}{p_i}\)