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

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

فرض کن دو تا عدد n و k بهت دادن. مسئله اینه که بزرگ‌ترین توان k، مثلا x، رو پیدا کنی که !n به k^x بخش‌پذیر باشه.

وقتی k یه عدد اوله

اول بیا ساده‌ترین حالت رو در نظر بگیریم: وقتی که k یه عدد اوله. فاکتوریل n رو که یادت هست، اینجوری باز میشه:

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

حالا یه نگاه به این ضرب بنداز. هر kاُمین عدد توی این ضرب، به k بخش‌پذیره (مثلاً اگه k=3 باشه، عددهای ۳، ۶، ۹ و...). هر کدوم از اینا حداقل یه عامل k به ما میدن. پس به ازای هر کدومشون، یه دونه به جوابمون اضافه میشه. تعداد این عددها چقدره؟ دقیقاً $\Bigl\lfloor\dfrac{n}{k}\Bigr\rfloor$ تا.

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

همین داستان رو ادامه میدیم. برای هر i، هر $k^i$-اُمین عدد، یه عامل k دیگه به ما میده که قبلاً حسابش نکردیم. تعداد اینا هم میشه $\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$$

به این فرمول خفن، فرمول لوژاندر (Legendre's formula) هم میگن. این جمعی که نوشتیم البته تا بی‌نهایت ادامه پیدا نمی‌کنه. یه جایی میرسه که $k^i$ از n بزرگتر میشه و حاصل تقسیم‌ها صفر میشه. در واقع فقط حدود $\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 رو به این شکل بنویسیم: $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}$$

چرا؟ فکر کن مثلاً $k = 12 = 2^2 \cdot 3^1$ باشه. برای ساختن هر یه دونه ۱۲، ما به دو تا ۲ و یه دونه ۳ نیاز داریم. حالا فرض کن توی !n، صد تا عامل ۲ و پنجاه تا عامل ۳ داریم. با این حساب، ما می‌تونیم $100/2 = 50$ تا $2^2$ بسازیم، ولی فقط ۵۰ تا ۳ داریم. پس در نهایت فقط می‌تونیم ۵۰ تا ۱۲ بسازیم، چون تعداد ۳ ها ما رو محدود کرده. برای همین مینیمم رو می‌گیریم.