如何找到比 On)
(n!) % m
更快的内容?
1 <= n <= 1e18
1 <= m <= 1e6
最佳答案
您可以轻松拥有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;
}
关于algorithm - 求阶乘 n 模 m 比 O(n) 更快,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/72246366/