پرش به محتویات

یافتن توان مقسوم‌علیهِ فاکتوریل

دو عدد n و k به شما داده شده است. بزرگ‌ترین توان k یعنی x را بیابید به طوری که !n بر k^x بخش‌پذیر باشد.

k اول

ابتدا حالتی را در نظر بگیریم که k عددی اول باشد. عبارت صریح برای فاکتوریل به این صورت است:

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

توجه داشته باشید که هر عنصر k-اُم در این حاصل‌ضرب بر k بخش‌پذیر است، یعنی ۱+ به جواب اضافه می‌کند؛ تعداد این عناصر برابر با $\Bigl\lfloor\dfrac{n}{k}\Bigr\rfloor$ است.

سپس، هر عنصر $k^2$-اُم بر $k^2$ بخش‌پذیر است، یعنی یک ۱+ دیگر به جواب اضافه می‌کند (توان اول k قبلاً در پاراگراف قبل شمرده شده است). تعداد این عناصر برابر با $\Bigl\lfloor\dfrac{n}{k^2}\Bigr\rfloor$ است.

و به همین ترتیب، برای هر i، هر عنصر $k^i$-اُم یک ۱+ دیگر به جواب اضافه می‌کند و تعداد این عناصر برابر با $\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)$ است.

پیاده‌سازی

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