Let \(n!_{\%p}\) be a special factorial where \(n!\) is divided by the maximum exponent of \(p\) that divides \(n!\)

\[ n!_{\%p} = \frac{n!}{d_p(n!)} \]

Where \(d_p(n!)\) is called Legendre's Formula which is explained in detail in this article

Compute \(n!_{\%p} \pmod{p}\) given that \(p\) is a prime number

First let's write this special factorial explicitely

\[ \begin{equation} \label{explicit} n!_{\%p} = \tfrac{1 \cdot 2 \cdot \ldots \cdot (p - 1) \cdot p \cdot (p + 1) \cdot \ldots \cdot (2p - 1) \cdot 2p \cdot (2p + 1) \cdot \ldots \cdot (kp - 1) \cdot kp \cdot (kp + 1) \cdot \ldots \cdot (n - 1) \cdot n}{p^{ \tfrac{n}{p} + \tfrac{n}{p^2} + ... }} \end{equation} \]

The number \(kp\) is a number that is divisible by \(p\), we also see that \(k\) might be a composite number that could be divisible by \(p\) again

Now let's first divide the equation by \(p^{ \tfrac{n}{p} }\) which is exactly the number of multiples of \(p\)

\[ n!_{\%p} = \tfrac{1 \cdot 2 \cdot \ldots \cdot (p - 1) \cdot 1 \cdot (p + 1) \cdot \ldots \cdot (2p - 1) \cdot 2 \cdot (2p + 1) \cdot \ldots \cdot (kp - 1) \cdot k \cdot (kp + 1) \cdot \ldots \cdot (n - 1) \cdot n}{p^{ \tfrac{n}{p^2} + ... }} \]

If we apply the modulo operation to each term except the multiples of \(p\) we have

\[ n!_{\%p} = \tfrac{1 \cdot 2 \cdot \ldots \cdot (p - 1) \cdot 1 \cdot 1 \cdot 2 \cdot \ldots \cdot (p - 1) \cdot 2 \cdot 1 \cdot 2 \cdot \ldots \cdot (p - 1) \cdot p \cdot 1 \cdot 2 \cdot \ldots \cdot (p - 1) \cdot kp}{p^{ \tfrac{n}{p^2} + ... }} \cdot 1 \cdot 2 \cdot \ldots \cdot (n - 1) \cdot n \]

NOTE: we're not applying the modulo operator to each multiple of \(p\) because they don't actually exist since there are no \(p\) factors in the equation, they are reduced with posterior divisions by \(p^{ \tfrac{n}{p^i} }\)

NOTE: the number \(kp\) described in \eqref{explicit} just denotes a multiple of \(p\)

We see that the expression \(1 \cdot 2 \cdot \ldots \cdot (p - 1)\) is repeated many times in the equation above + a product of some additional terms which don't form an entire sequence, let \(c = 1 \cdot 2 \cdot \ldots \cdot (p - 1)\) then

\[ n!_{\%p} = \tfrac{1c \cdot 2c \cdot \ldots \cdot (p - 1)c \cdot pc \cdot (p + 1)c \cdot \ldots \cdot (kp - 1)c \cdot kpc}{p^{ \tfrac{n}{p^2} + ... }} \cdot 1 \cdot 2 \cdot \ldots \cdot (n - 1) \cdot n \]

Since each \(c\) factor occurs in every contiguous sequence of length \(p\) there are exactly \(\left \lfloor \tfrac{n}{p} \right \rfloor\) \(c\) factors, factoring \(c\) we have

\[ n!_{\%p} = c^{\left \lfloor \tfrac{n}{p} \right \rfloor} \cdot \tfrac{1 \cdot 2 \cdot \ldots \cdot (p - 1) \cdot p \cdot (p + 1) \cdot \ldots \cdot (2p - 1) \cdot 2p \cdot (2p + 1) \cdot \ldots \cdot (kp - 1) \cdot kp}{p^{ \tfrac{n}{p^2} + ... }} \cdot 1 \cdot 2 \cdot \ldots \cdot (n - 1) \cdot n \]

Note that the term multiplying \(c^{\left \lfloor \tfrac{n}{p} \right \rfloor}\) is the same as \eqref{explicit}, we now have to divide it by \(p^{ \tfrac{n}{p^2} }\) which is exactly the number of multiples of \(p^2\) (NOTE: \(kp\) is a multiple of \(p\) but might/might not be a multiple of \(p^2\))

This observation leads to a recursive implementation

Complexity: \(O(p \, log_p{n})\)

long long special_factorial_mod_p(long long n, long long p) {
  long long res = 1;

  // computation of c
  long long c = 1;
  for (long long i = 2; i < n % p; i += 1) {
    c = (c * i) % p;
  }

  while (n > 1) {
    res = (res * binary_exponentiation_modulo_m(c, n / p, p)) % p;
    for (long long i = 2; i < n % p; i += 1) {
      res = (res * (long long)i) % p;
    }
    n /= p;
  }
  return res % p;
}

Applications

Finding the value of \(nCr \% p\)

We can quickly calculate the value of \(nCr \% p\), we can compute the maximum exponents of \(p\) in \(n!\), \((n - r)!\) and \(r!\), let those numbers be \(p^a\), \(p^b\) and \(p^c\) then \(nCr\) can be expressed as

\[ nCr = \binom{p^a \cdot \ldots}{p^b \cdot p^c \ldots} \]

Which means that \(nCr\) will be a multiple of \(p\) when \(a - b - c > 0\), if \(a - b - c = 0\) then the number is equal to

\[ nCr = \frac{n!_{\%p}}{(n - r)!_{\%p} \cdot r!_{\%p}} \]

NOTE: \(a - b - c\) can never be less than zero, that would imply that \(nCr\) is not an integer

The denominator can be found using the modular multiplicative inverse of \((n - r)!_{\%p}\) and \(r!_{\%p}\)

long long nCr_mod_p(int n, int r, int p) {
  int a = max_power_in_factorial(n, p);
  int b = max_power_in_factorial(n - r, p);
  int c = max_power_in_factorial(r, p);
  if (a > b + c) {
    return 0;
  }

  return (special_factorial_mod_p(n, p) *
    ((modular_multiplicative_inverse(special_factorial_mod_p(n - r, p), p) *
    modular_multiplicative_inverse(special_factorial_mod_p(r, p), p)) % p) % p);
}

Problems to solve