peltorator

Часто в задачах бывает необходимо искать $n! \bmod p$. Обычно модуль — это большое число, а $n$ не очень большое, поэтому можно просто заранее предпосчитать все факториалы. Однако иногда бывает обратная ситуация: $p < n$. С первого взгляда кажется, что это бессмысленная задача: в $n!$ в таком случае входит число $p$, поэтому $n! \bmod p = 0$. Но часто нас не устраивает такой ответ, потому что нам часто нужно делить факториалы друг на друга. В этом случае мы можем получить выражения типа $\frac{0}{0}$, которое на самом деле равно чему-то ненулевому. Встает задача: посчитать $n! \bmod p$ без вхождений $p$ в $n!$ и отдельно посчитать степень вхождения $p$ в факториал, то есть представить $n!$ в виде $a \cdot p^k$, где $a$ не делится на $p$.

Пускай $\left\lfloor \frac{n}{p} \right\rfloor = k$ и $n \bmod p = b$. Тогда

$$n! = (1 \cdot 2 \cdot \ldots \cdot (p - 1)) \cdot p \cdot ((p + 1) \cdot (p + 2) \cdot \ldots \cdot (2p - 1)) \cdot (2p) \cdot \ldots \cdot (kp) \cdot ((kp + 1) \cdot \ldots \cdot (kp + b))$$

Если брать это по модулю $p$, то получится

$$(p - 1)! \cdot p \cdot (p - 1)! \cdot (2p) \cdot \ldots \cdot (p - 1)! \cdot (kp) \cdot b! = \left((p - 1)!\right)^k \cdot b! \cdot (k! \cdot p^k)$$

При этом $p^k$ мы игнорируем, потому что это вхождения $p$.

По теореме Вильсона $(p - 1)! \bmod p = -1$. Так что нам необходимо посчитать $(-1)^k \cdot b! \cdot k!$. При этом $b < p$ (это остаток от деления на $p$), так что $b!$ можно посчитать за $O(p)$, после чего рекурсивно запуститься для подсчета $k!$. Каждый раз мы делим число $n$ на $p$, так что будет всего $\log_p n = \frac{\log n}{\log p}$ итераций. Асимптотика — $O(p \log_p n)$. С другой стороны, все факториалы до $p$ можно предпосчитать заранее, и тогда асимптотика будет $O(\log_p n)$ на запрос и $O(p)$ на предпосчет.

Реализация представлена ниже:

int mod_factorial(long long n, int p) {
    int factorial = 1;
    while (n > 0) {
        long long k = n / p;
        int b = n % p;
        if (k % 2 == 1) {
            factorial = 1LL * factorial * (p - 1) % p;
        }
        for (int i = 1; i <= b; i++) {
            factorial = 1LL * factorial * i % p;
        }
        n = k;
    }
    return factorial;
}

С другой стороны, если нам надо посчитать степень вхождения $p$ в факториал, это делается еще проще. Давайте для этого посчитаем количество чисел, которые делятся на $p$, на $p^2$, на $p^3$ и т.д. И тогда если число делится ровно на $p^k$, то мы учтем его как раз $k$ раз. А если заметить, что количество чисел, делящихся на $p^i$, — это $\left\lfloor \frac{n}{p^i} \right\rfloor$, то получается такой незатейливый алгоритм:

int factorial_power(int n, int p) {
    int power = 0;
    while (n > 0) {
        n /= p;
        power += n;
    }
    return power;
}

Асимптотика равна $O(\log_p n)$.