$p$ модулиар факториал¶

Зарим тохиолдолд Биномын коэффициентийн томьёонд тааралддаг шиг хүртвэр ба хуваарь хоёуланд нь факториал агуулсан нийлмэл томьёог ямар нэг анхны тоо $p$ модулиар авч үзэх шаардлагатай болдог. Бид $p$ харьцангуй бага байх тохиолдлыг авч үзнэ. Энэ бодлого зөвхөн факториал бутархайн хүртвэр ба хуваарь хоёуланд нь гарч ирэх үед л утга учиртай. Эс бөгөөс $p!$ ба түүнээс хойших гишүүд тэг болж хураагдана. Гэвч бутархайд $p$ үржигдэхүүнүүд хураагдаж, үр дүнгийн илэрхийлэл $p$ модулиар тэгээс ялгаатай болно.

Тиймээс албан ёсоор бодлого нь: факториалд гарч ирэх $p$-ийн бүх үржигдэхүүнийг тооцолгүйгээр $n! \bmod 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}_{1\text{st}} \cdot \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 2}_{2\text{nd}} \cdot \ldots \\\\ & & \cdot \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 1}_{p\text{th}} \cdot \ldots \cdot \quad \underbrace{1 \cdot 2 \cdot \cdot \ldots \cdot (n \bmod p)}_{\text{tail}} \pmod{p}. \end{eqnarray}$$

Блокуудын үндсэн хэсгийг тоолоход амархан — энэ бол зүгээр л $(p-1)!\ \mathrm{mod}\ p$ юм. Үүнийг программаар тооцоолж болно, эсвэл дурын анхны тоо $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$ модулиар урьдчилан тооцоолвол complexity нь ердөө $O(\log_p n)$ болохыг анхаараарай.

Implementation¶

We don't need recursion because this is a case of tail recursion and thus can be easily implemented using iteration. In the following implementation we precompute the factorials $0!,~ 1!,~ \dots,~ (p-1)!$, and thus have the runtime $O(p + \log_p n)$. If you need to call the function multiple times, then you can do the precomputation outside of the function and do the computation of $n!_{\%p}$ in $O(\log_p n)$ time.

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

Alternative, if you only have limit memory and can't afford storing all factorials, you can also just remember the factorials that you need, sort them, and then compute them in one sweep by computing the factorials $0!,~ 1!,~ 2!,~ \dots,~ (p-1)!$ in a loop without storing them explicitly.

$p$-ийн олонлогийн зэрэг¶

Хэрэв бид Биномын коэффициентийг $p$ модулиар тооцоолохыг хүсвэл нэмж $n$ дэх $p$-ийн зэргийг, өөрөөр хэлбэл $n$-ийн анхны үржигдэхүүнд задаргаанд $p$ хэдэн удаа тохиолдохыг, эсвэл өөрчилсөн факториалыг тооцоолох явцад бид $p$-г хэдэн удаа устгасныг мэдэх хэрэгтэй.

Лежандрын томьёо нь үүнийг $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 !$ үржвэрийг авах ба дахин рекурс үүснэ.