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

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

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

بنابراین، به طور رسمی، وظیفه این است: می‌خواهیم $!n \bmod p$ را محاسبه کنیم، بدون اینکه تمام عوامل مضرب $p$ را که در فاکتوریل ظاهر می‌شوند در نظر بگیریم. تصور کنید که تجزیه به عوامل اول $!n$ را می‌نویسید، تمام عوامل $p$ را حذف می‌کنید و حاصل‌ضرب را به پیمانه‌ی $p$ محاسبه می‌کنید. ما این فاکتوریل اصلاح‌شده را با $n!_{\%p}$ نشان خواهیم داد. برای مثال، $7!_{\%p} \equiv 1 \cdot 2 \cdot \underbrace{1}_{3} \cdot 4 \cdot 5 \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)!\ \mathrm{mod}\ p$ است. می‌توانیم آن را به صورت برنامه‌نویسی محاسبه کنیم یا فقط از قضیه‌ی ویلسون (Wilson's theorem) استفاده کنیم که بیان می‌کند برای هر عدد اول $p$، داریم $(p-1)! \bmod p = -1$.

ما دقیقاً $\lfloor \frac{n}{p} \rfloor$ بلوک از این نوع داریم، بنابراین باید $-1$ را به توان $\lfloor \frac{n}{p} \rfloor$ برسانیم. این کار را می‌توان در زمان لگاریتمی با استفاده از توان‌رسانی دودویی انجام داد؛ با این حال، می‌توانید متوجه شوید که نتیجه بین $-1$ و $1$ تغییر می‌کند، بنابراین فقط باید به زوجیت توان نگاه کنیم و اگر توان فرد بود، در $-1$ ضرب کنیم. و به جای ضرب، می‌توانیم نتیجه فعلی را از $p$ کم کنیم.

مقدار بلوک جزئی آخر را می‌توان به طور جداگانه در $O(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$ از قبل محاسبه کنید، پیچیدگی زمانی به $O(\log_p n)$ کاهش می‌یابد.

پیاده‌سازی

ما به بازگشت نیازی نداریم زیرا این یک مورد بازگشت از انتها (tail recursion) است و بنابراین می‌توان آن را به راحتی با استفاده از حلقه پیاده‌سازی کرد. در پیاده‌سازی زیر، ما فاکتوریل‌های $!0, ~!1, \dots, !(p-1)$ را از قبل محاسبه می‌کنیم و در نتیجه زمان اجرا $O(p + \log_p n)$ خواهد بود. اگر نیاز دارید تابع را چندین بار فراخوانی کنید، می‌توانید پیش‌محاسبات را خارج از تابع انجام دهید و محاسبه‌ی $n!_{\%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;
}

به عنوان راه حل جایگزین، اگر حافظه محدودی دارید و نمی‌توانید تمام فاکتوریل‌ها را ذخیره کنید، می‌توانید فقط فاکتوریل‌هایی را که نیاز دارید به خاطر بسپارید، آنها را مرتب کنید و سپس با محاسبه فاکتوریل‌های $!0, ~!1, ~!2, \dots, !(p-1)$ در یک حلقه و بدون ذخیره‌سازی صریح، آنها را در یک مرحله محاسبه کنید.

تعداد تکرار عامل $p$

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

فرمول لژاندر (Legendre's formula) راهی برای محاسبه‌ی این مقدار در زمان $O(\log_p n)$ به ما می‌دهد. این فرمول تعداد تکرار $\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$ را ندارند حذف کنید. با این کار، $\lfloor n/p \rfloor$ عنصر باقی می‌ماند. اگر عامل $p$ را از هر یک از آنها حذف کنیم، به حاصل‌ضرب $1 \cdot 2 \cdots \lfloor n/p \rfloor = \lfloor n/p \rfloor !$ می‌رسیم و دوباره با یک رابطه‌ی بازگشتی مواجه می‌شویم.