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

محاسبه فاکتوریل به پیمانه $p$

بعضی وقتا پیش میاد که باید یه سری فرمول‌های پیچیده رو به پیمانه یه عدد اول $p$ حساب کنیم. منظورم فرمول‌هاییه که تو صورت و مخرجشون فاکتوریل دارن، مثل فرمول ضریب دو جمله‌ای.

ما اینجا حالتی رو در نظر می‌گیریم که $p$ نسبتاً کوچیک باشه. ببین، این مسئله فقط وقتی معنی پیدا می‌کنه که فاکتوریل‌ها هم توی صورت کسر باشن و هم توی مخرجش. چرا؟ چون اگه اینطور نباشه، از $p!$ به بعد، همه چی به پیمانه $p$ صفر میشه. ولی وقتی کسر داریم، عامل‌های $p$ می‌تونن با هم ساده بشن و جواب نهایی به پیمانه $p$ یه عدد غیرصفر باشه.

خب، پس اگه بخوایم رسمی‌تر بگیم، کار ما اینه: می‌خوایم $n! \bmod p$ رو حساب کنیم، ولی با این شرط که تمام عامل‌هایی که مضرب $p$ هستن رو نادیده بگیریم. فکر کن داری $n!$ رو به عامل‌های اولش تجزیه می‌کنی، بعد میای هرچی عامل $p$ هست رو از توش حذف می‌کنی و باقی‌مونده رو به پیمانه $p$ حساب می‌کنی. ما به این فاکتوریل دستکاری شده یا اصلاح‌شده میگیم $n!_{\%p}$. مثلاً $7!_{\%3}$ اینجوری میشه: $7!_{\%3} \equiv 1 \cdot 2 \cdot \underbrace{1}_{3} \cdot 4 \cdot 5 \cdot \underbrace{2}_{6} \cdot 7 \equiv 2 \bmod 3$.

اگه یاد بگیریم چطوری این فاکتوریل اصلاح‌شده رو سریع حساب کنیم، اون‌وقت می‌تونیم مقدار یه عالمه فرمول ترکیبیاتی دیگه (مثلاً ضریب‌های دوجمله‌ای) رو هم با سرعت بالا به دست بیاریم.

الگوریتم

بیا این فاکتوریل اصلاح‌شده رو با جزئیات بنویسیم تا ببینیم چی به چیه.

$$\begin{eqnarray} n!_{\%p} &=& 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot \underbrace{1}_{p} \cdot (p+1) \cdot (p+2) \cdot \ldots \cdot (2p-1) \cdot \underbrace{2}_{2p} \\\ & &\quad \cdot (2p+1) \cdot \ldots \cdot (p^2-1) \cdot \underbrace{1}_{p^2} \cdot (p^2 +1) \cdot \ldots \cdot n \pmod{p} \\\\ &=& 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot \underbrace{1}_{p} \cdot 1 \cdot 2 \cdot \ldots \cdot (p-1) \cdot \underbrace{2}_{2p} \cdot 1 \cdot 2 \\\ & &\quad \cdot \ldots \cdot (p-1) \cdot \underbrace{1}_{p^2} \cdot 1 \cdot 2 \cdot \ldots \cdot (n \bmod p) \pmod{p} \end{eqnarray}$$

همونطور که می‌بینی، فاکتوریل ما به چندتا بلوک با طول یکسان تقسیم شده، البته به جز بلوک آخری که ممکنه ناقص باشه.

$$\begin{eqnarray} n!_{\%p}&=& \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 1}_{\text{بلوک اول}} \cdot \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 2}_{\text{بلوک دوم}} \cdot \ldots \\\\ & & \cdot \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 1}_{\text{بلوک p-ام}} \cdot \ldots \cdot \quad \underbrace{1 \cdot 2 \cdot \cdot \ldots \cdot (n \bmod p)}_{\text{بخش انتهایی}} \pmod{p}. \end{eqnarray}$$

حساب کردن بخش اصلی هر بلوک خیلی راحته. این بخش در واقع همون $(p-1)! \pmod p$ خودمونه. می‌تونیم اینو با کد حساب کنیم، یا خیلی راحت‌تر، از قضیه ویلسون (Wilson's theorem) استفاده کنیم. این قضیه میگه برای هر عدد اول $p$، داریم: $(p-1)! \equiv -1 \pmod p$.

ما دقیقاً $\lfloor \frac{n}{p} \rfloor$ تا از این بلوک‌های کامل داریم، پس باید $(p-1)!$ رو $\lfloor \frac{n}{p} \rfloor$ بار در هم ضرب کنیم، که یعنی همون $(-1)^{\lfloor n/p \rfloor}$. این توان رو میشه با توان‌رسانی سریع (Binary Exponentiation) توی زمان لگاریتمی حساب کرد. ولی یه راه ساده‌تر هم هست: نتیجه این توان یا $1$ میشه یا $-1$. پس کافیه فقط زوج یا فرد بودن توان رو چک کنیم. اگه توان فرد بود، نتیجه رو در $-1$ ضرب می‌کنیم. تازه به جای ضرب در $-1$ هم می‌تونیم نتیجه فعلی رو از $p$ کم کنیم (چون $x \cdot (-1) \equiv -x \equiv p-x \pmod p$).

حاصل‌ضرب تیکه‌ی آخر (بلوک ناقص) رو هم می‌تونیم جداگونه توی $O(p)$ حساب کنیم.

خب، تا اینجا حاصل‌ضرب داخل هر بلوک رو حساب کردیم. حالا چی مونده؟ از هر بلوک، فقط اون عامل آخریش مونده که از تقسیم بر $p$ به دست اومده بود. اگه عددهایی که حساب کردیم رو کنار بذاریم، با یه همچین الگویی روبرو میشیم:

$$n!_{\%p} = \underbrace{ \ldots \cdot 1 } \cdot \underbrace{ \ldots \cdot 2} \cdot \ldots \cdot \underbrace{ \ldots \cdot (p-1)} \cdot \underbrace{ \ldots \cdot 1 } \cdot \underbrace{ \ldots \cdot 1} \cdot \underbrace{ \ldots \cdot 2} \cdots$$

اینا رو که کنار هم بذاری، می‌بینی که این خودش دوباره یه فاکتوریل اصلاح‌شده است، ولی برای یه عدد خیلی کوچیکتر! در واقع این همون $\lfloor n / p \rfloor !_{\%p}$ خودمونه.

پس داستان این شد: برای محاسبه $n!_{\%p}$، ما یه سری محاسبات توی $O(p)$ انجام میدیم و مسئله رو به محاسبه‌ی $\lfloor n / p \rfloor !_{\%p}$ تبدیل می‌کنیم. این یعنی یه فرمول بازگشتی داریم! عمق این بازگشت هم $O(\log_p n)$ هست. پس پیچیدگی زمانی کل الگوریتم میشه $O(p \log_p n)$.

یه نکته: اگه فاکتوریل‌های $0!, 1!, 2!, \dots, (p-1)!$ رو به پیمانه $p$ از قبل حساب کنی (precompute)، پیچیدگی زمانی الگوریتم خیلی بهتر میشه و به $O(\log_p n)$ میرسه.

پیاده‌سازی

برای پیاده‌سازی، لازم نیست حتماً از تابع بازگشتی استفاده کنیم. چون این یه مدل بازگشت از انتها (tail recursion) هست، خیلی راحت میشه با یه حلقه while تبدیلش کرد به یه کد غیربازگشتی. توی کد زیر، ما فاکتوریل‌های $0!, 1!, \dots, (p-1)!$ رو از قبل حساب می‌کنیم. برای همین، زمان اجرا میشه $O(p + \log_p n)$ (اون $O(p)$ برای پیش‌محاسبه است). اگه قرار باشه این تابع رو چند بار صدا بزنی، می‌تونی بخش پیش‌محاسبه رو یه بار بیرون از تابع انجام بدی تا هر بار فراخوانی فقط $O(\log_p n)$ طول بکشه.

int factmod(int n, int p) {
    vector<int> f(p);
    f[0] = 1;
    for (int i = 1; i < p; i++)
        f[i] = f[i-1] * i % p;

    int res = 1;
    while (n > 1) {
        if ((n/p) % 2)
            res = p - res;
        res = res * f[n%p] % p;
        n /= p;
    }
    return res;
}

یه راه حل جایگزین هم هست برای وقتی که حافظه محدوده و نمی‌تونی همه فاکتوریل‌ها رو توی یه آرایه ذخیره کنی. می‌تونی به جای این کار، فقط اون باقی‌مونده‌هایی که لازم داری (n%p توی هر مرحله) رو یه جا یادداشت کنی، بعد مرتبشون کنی و توی یه حلقه، فاکتوریل‌ها رو تا جایی که لازمه حساب کنی و جواب‌ها رو به دست بیاری. اینجوری دیگه نیازی به ذخیره کل آرایه فاکتوریل‌ها نیست.

چند بار عامل $p$ تکرار شده؟

اگه بخوایم یه چیزی مثل ضریب دوجمله‌ای رو به پیمانه $p$ حساب کنیم، علاوه بر فاکتوریل اصلاح‌شده، باید بدونیم خود عامل $p$ چند بار توی $n!$ ظاهر شده. به عبارت دیگه، توان $p$ توی تجزیه $n!$ به عوامل اول چنده؟ یا اگه از زاویه دیگه نگاه کنیم، همون تعداد دفعاتی که ما مضرب‌های $p$ رو موقع حساب کردن فاکتوریل اصلاح‌شده حذف کردیم.

فرمول لژاندر (Legendre's formula) یه راه خیلی سریع برای حساب کردن این تعداد به ما میده که پیچیدگیش $O(\log_p n)$ هست. این فرمول میگه تعداد تکرار $p$ (که با $\nu_p$ نشونش میدیم) اینجوری به دست میاد:

$$\nu_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor$$

پس پیاده‌سازیش میشه یه همچین چیزی:

int multiplicity_factorial(int n, int p) {
    int count = 0;
    do {
        n /= p;
        count += n;
    } while (n);
    return count;
}

اثبات این فرمول هم خیلی ساده‌ است و دقیقاً از همون ایده‌هایی استفاده می‌کنه که بالاتر دیدیم. فکر کن تمام عددهایی که به $p$ بخش‌پذیر نیستن رو حذف می‌کنی. چی می‌مونه؟ $p, 2p, 3p, \dots, \lfloor n/p \rfloor \cdot p$. تعداد اینا $\lfloor n/p \rfloor$ تاست. حالا اگه از همشون یه عامل $p$ فاکتور بگیریم، به حاصل‌ضرب $1 \cdot 2 \cdot 3 \cdots \lfloor n/p \rfloor$ می‌رسیم که همون $\lfloor n/p \rfloor !$ خودمونه. اینجوری دوباره به یه رابطه بازگشتی می‌رسیم که همون فرمول لژاندر رو نتیجه میده.