Факториалын хуваагчийн зэргийг олох¶

Танд $n$ ба $k$ гэсэн хоёр тоо өгөгдсөн. $k^x$ нь $n!$-г хуваах хамгийн их бүхэл тоо $x$-г ол.

Анхны $k$¶

Эхлээд анхны $k$-ийн тохиолдлыг авч үзье. Факториалын шууд илэрхийлэл

$$n! = 1 \cdot 2 \cdot 3 \ldots (n-1) \cdot n$$

Үржвэрийн $k$ дэх элемент бүр $k$-д хуваагдана, өөрөөр хэлбэл хариуд $+1$ нэмнэ гэдгийг анхаарна уу; ийм элементийн тоо нь $\Bigl\lfloor\dfrac{n}{k}\Bigr\rfloor$.

Дараа нь $k^2$ дэх элемент бүр $k^2$-д хуваагдана, өөрөөр хэлбэл хариуд дахин $+1$ нэмнэ ($k$-ийн эхний зэргийг өмнөх догол мөрөнд аль хэдийн тоолсон). Ийм элементийн тоо нь $\Bigl\lfloor\dfrac{n}{k^2}\Bigr\rfloor$.

Ингэсээр $i$ бүрийн хувьд $k^i$ дэх элемент бүр хариуд дахин $+1$ нэмэх ба ийм элемент $\Bigl\lfloor\dfrac{n}{k^i}\Bigr\rfloor$ ширхэг байна.

Эцсийн хариу нь

$$\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$$

Энэ үр дүнг Лежандрын томьёо гэж бас нэрлэдэг. Нийлбэр мэдээж төгсгөлөг, учир нь ойролцоогоор эхний $\log_k n$ элемент л тэг биш байна. Тиймээс энэ алгоритмын ажиллах хугацаа нь $O(\log_k n)$.

Implementation¶

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

Нийлмэл $k$¶

Ижил санааг шууд хэрэглэж болохгүй. Оронд нь бид $k$-г үржигдэхүүнд задалж, $k = k_1^{p_1} \cdot \ldots \cdot k_m^{p_m}$ хэлбэрээр илэрхийлж болно. $k_i$ бүрийн хувьд дээр тайлбарласан алгоритмыг ашиглан түүнийг $n!$-д хэдэн удаа орсныг олно — энэ утгыг $a_i$ гэж нэрлэе. Нийлмэл $k$-ийн хариу нь

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

болно.