Finding modulus when all power of p are removed from N!

Question

Given two integers $p$ and $N$. Let $m$ be number by $N!$ by max power of $p$ which divided $N!$. We have to find $m$ mod $p$. How to solve this?

Answer 1

The contest being over by now, here's my solution.

I assume, as in the original problem, that $p$ is a prime.

First you have the product of all $i \in \{1, \dots, N \}$ which are coprime to $p$. Since $$(p-1)! \equiv -1 \pmod{p},\tag{Wilson}$$ this will be $$ (-1)^{a_0} \cdot 1 \cdot 2 \cdot \dots \cdot b_{0} \pmod{p} $$ if $N = a_0 p + b_0$, with $0 \le b_0 < p$. Note that $$ a_{0} = \left\lfloor \frac{N}{p} \right\rfloor. $$

Then there is the contribution coming from all the numbers that are divisible by $p$ but not $p^2$. If $$a_{0} = a_1 p + b_1$$ with $0 \le b_1 < p$, then by (Wilson) they contribute $$ (-1)^{a_1} b_1! \pmod{p}. $$ Then there are the terms divisible by $p^2$ but not $p^3$, etc.

All in all, it seems we get $$ \prod_{i=0}^{\dots} (-1)^{a_i} b_i! \pmod{p}, $$ where $$\left\lfloor \frac{N}{p^i} \right\rfloor = a_i p + b_i$$ for $i \ge 0$, and $0 \le b_i < p$, or, recursively, $N = a_0 p + b_0$, and then $a_{i-1} = a_i p + b_i$ for $i \ge 1$, with $0 \le b_{i} < p$ for all $i \ge 0$. The $b_i$ are thus the coefficients of the representation of $N$ in base $p$. Note that in the product we stop with the $i$-th term when first $a_i = 0$.

This is a GAP program to compute the result. For large $p$ one should compute the factorial in a smarter way, at the very least with intermediate reductions modulo $p$. With this variation, on my oldish machine the code appears to run in a competitive time with respect to the requirements of the problem.

function ( n, p )
    local  a, b, curr, res;
    curr := n;
    res := 1;
    while curr > 0  do
        a := EuclideanQuotient( curr, p );
        b := EuclideanRemainder( curr, p );
        res := res * (-1)^(a mod 2) * Factorial( b ) mod p;
        curr := a;
    od;
    return res;
end