Find factorial n modulo m faster than O(n)-CodePudding

How can I find (n!) % m faster than O(n)?

1 <= n <= 1e18

1 <= m <= 1e6

CodePudding user response：

You can easily have O(m) time complexity in the worst case (when m is a prime) and it seems to be good enough since you have m <= 1e6 (while n can be up to 1e18). Note, that when n >= m

 n! = 1 * 2 * ... * m * ... * n
                    ^
         factorial is divisible by m

and that's why

 n! % m == 0       # whenever n >= m

Another implementation detail is that you don't have to compute n! % m as 1 * 2 * ... * n % m but you can do it as ((..(1 % m) * 2 % m) ... * n % m) in order not to deal with huge numbers.

C# code example

private static int Compute(long n, long m) {
  if (n >= m)
    return 0;

  long result = 1;

  // result != 0 - we can well get 0 and stop looping when m is not prime 
  for (long d = 2; d <= n && result != 0;   d) 
    result = (result * d) % m;

  return result;
}

CodePudding user response：

As explained by Dmitry, you can suppose than m<n. Let p1....pk the list of primes smaller or equal to m. Then m! mod n=(p1^a1.p2^a2....pk^ak)mod n=(p1^a1)mod n.(p2^a2 mod n)....(pk ^ak mod n) (mod n) for some a1.... ak that I'll let you find by yourself.

Using https://en.wikipedia.org/wiki/Modular_exponentiation, you can then compute m! (mod n).