比 O(n) 更快地找到阶乘 n 模 m

Question

如何找到 (n!) % m 比 O(n) 更快？

1 <= n <= 1e18

1 <= m <= 1e6

Answer 1

在最坏的情况下（当 m 是 prime 时）你可以很容易地拥有 O(m) 时间复杂度，而且它似乎已经足够好了，因为你有 m <= 1e6（而 n 最多可达 1e18）。请注意，当 n >= m

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

这就是为什么

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

另一个实现细节是您不必将 n! % m 计算为 1 * 2 * ... * n % m 但您可以将其计算为 ((..(1 % m) * 2 % m) ... * n % m)为了不处理巨大的数字。

C#代码示例

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

Answer 2

正如 Dmitry 所解释的，您可以假设 m

使用https://en.wikipedia.org/wiki/Modular_exponentiation，然后您可以计算 m！ (modn).

比 O(n) 更快地找到阶乘 n 模 m

Find factorial n modulo m faster than O(n)

algorithm

math

factorial