algorithm - 求阶乘 n 模 m 比 O(n) 更快

Question

如何找到比 On) (n!) % m 更快的内容？

1 <= n <= 1e18

1 <= m <= 1e6

Answer 1

您可以轻松拥有O(m)最坏情况下的时间复杂度(当 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;
}