我很好奇是否有一个好的方法来做到这一点。我当前的代码是这样的：
def factorialMod(n, modulus):
ans=1
for i in range(1,n+1):
ans = ans * i % modulus
return ans % modulus
但它似乎很慢！
我也无法计算n！然后应用素数模数，因为有时 n 太大以至于 n！明确计算是不可行的。
我还遇到了http://en.wikipedia.org/wiki/Stirling%27s_approximation并且想知道这是否可以以某种方式在这里使用？
或者，我如何在 C++ 中创建一个递归的、记忆化的函数？
n 可以任意大
好吧，n不能任意大 - 如果n >= m，则n! ≡ 0 (mod m) （因为m是因子之一，根据阶乘的定义）。
假设n << m并且您需要一个确切的值，据我所知，您的算法不会变得更快。但是，如果n > m/2，您可以使用以下身份（威尔逊定理- 谢谢@Daniel Fischer！）
将乘法次数限制在大约m-n
（米-1）！≡ -1 (mod m) 1 * 2 * 3 * ... * (n-1) * n * (n+1) * ... * (m-2) * (m-1) ≡ -1 (mod m) 嗯！* (n+1) * ... * (m-2) * (m-1) ≡ -1 (mod m) 嗯！≡ -[(n+1) * ... * (m-2) * (m-1)] -1 (mod m)
这为我们提供了一种简单n! (mod m)的m-n-1乘法计算方法，以及模逆：
def factorialMod(n, 模数):
答案=1
如果 n <= 模数//2：
#正常计算阶乘（range() 的右参数是独占的）
对于范围内的 i (1,n+1)：
ans = (ans * i) % 模数
别的：
#大n的Fancypants方法
对于范围内的 i（n+1，模数）：
ans = (ans * i) % 模数
ans = modinv（ans，模数）
ans = -1*ans + 模数
返回 ans % 模数
我们可以用另一种方式改写上述等式，这可能会或可能不会执行得稍微快一些。使用以下身份：
我们可以将方程改写为
嗯！≡ -[(n+1) * ... * (m-2) * (m-1)] -1 (mod m)
嗯！≡ -[(n+1-m) * ... * (m-2-m) * (m-1-m)] -1 (mod m)
（术语的倒序）
嗯！≡ -[(-1) * (-2) * ... * -(mn-2) * -(mn-1)] -1 (mod m)
嗯！≡ -[(1) * (2) * ... * (mn-2) * (mn-1) * (-1) (mn-1) ] -1 (mod m)
嗯！≡ [(mn-1)!] -1 * (-1) (mn) (mod m)
这可以用 Python 编写如下：
def factorialMod(n, 模数):
答案=1
如果 n <= 模数//2：
#正常计算阶乘（range() 的右参数是独占的）
对于范围内的 i (1,n+1)：
ans = (ans * i) % 模数
别的：
#大n的Fancypants方法
对于范围内的 i（1，模数-n）：
ans = (ans * i) % 模数
ans = modinv（ans，模数）
#因为m是奇素数，(-1)^(mn) = -1如果n是偶数，+1如果n是奇数
如果 n % 2 == 0：
ans = -1*ans + 模数
返回 ans % 模数
如果您不需要精确的值，生活会轻松一些 - 您可以使用斯特林的近似值O(log n)及时计算近似值（使用平方取幂）。
最后，我应该提一下，如果这是时间紧迫的，并且您使用的是 Python，请尝试切换到 C++。根据个人经验，您应该期望速度会提高一个数量级或更多，仅仅是因为这正是本机编译代码擅长的那种受 CPU 限制的紧密循环（此外，无论出于何种原因，GMP 似乎比 Python 的 Bignum 更精细）。
将我的评论扩展到答案：
是的，有更有效的方法可以做到这一点。但它们非常混乱。
所以除非你真的需要额外的性能，否则我不建议尝试实现这些。
关键是要注意模数（本质上是一个除法）将成为瓶颈操作。幸运的是，有一些非常快速的算法可以让你多次对相同的数字进行取模。
这些方法很快，因为它们基本上消除了模量。
仅这些方法就可以为您带来适度的加速。为了真正高效，您可能需要展开循环以实现更好的 IPC：
像这样的东西：
ans0 = 1
ans1 = 1
for i in range(1,(n+1) / 2):
ans0 = ans0 * (2*i + 0) % modulus
ans1 = ans1 * (2*i + 1) % modulus
return ans0 * ans1 % modulus
但考虑到奇数的迭代次数并将其与我上面链接的方法之一结合起来。
有些人可能会争辩说，循环展开应该留给编译器。我会反驳说编译器目前还不够聪明，无法展开这个特定的循环。仔细看看，你就会明白为什么。
请注意，尽管我的回答与语言无关，但它主要用于 C 或 C++。
嗯！mod m 可以在 O(n 1/2 + ε ) 操作中计算，而不是简单的 O(n)。这需要使用 FFT 多项式乘法，并且仅适用于非常大的 n，例如 n > 10 4。
该算法的概要和一些时间安排可以在这里看到：http: //fredrikj.net/blog/2012/03/factorials-mod-n-and-wilsons-theorem/
如果我们想计算M = a*(a+1) * ... * (b-1) * b (mod p)，我们可以使用下面的方法，如果我们假设我们可以快速加减乘乘（mod p），得到一个运行时间复杂度O( sqrt(b-a) * polylog(b-a) )。
为简单起见，假设(b-a+1) = k^2是一个正方形。现在，我们可以将我们的产品分成 k 个部分，即M = [a*..*(a+k-1)] *...* [(b-k+1)*..*b]。本产品中的每一个因素都是形式p(x)=x*..*(x+k-1)，为宜x。
通过使用多项式的快速乘法算法，例如Schönhage-Strassen 算法，以分治法的方式，可以找到多项式的系数p(x) in O( k * polylog(k) )。现在，显然有一种算法可以用k相同的 k 次多项式代替 中的点O( k * polylog(k) )，这意味着我们可以p(a), p(a+k), ..., p(b-k+1)快速计算。
这种将许多点代入一个多项式的算法在 C. Pomerance 和 R. Crandall 的“素数”一书中进行了描述。最终，当您拥有这些k值时，您可以将它们相乘O(k)并获得所需的值。
请注意，我们所有的操作都是在哪里进行的(mod p)。确切的运行时间是O(sqrt(b-a) * log(b-a)^2 * log(log(b-a)))。
扩展我的评论，对于 [100, 100007] 中的所有 n，这需要大约 50% 的时间，其中 m=(117 | 1117)：
Function facmod(n As Integer, m As Integer) As Integer
Dim f As Integer = 1
For i As Integer = 2 To n
f = f * i
If f > m Then
f = f Mod m
End If
Next
Return f
End Function
我在 quora 上找到了以下函数：
With f(n,m) = n! 模米；
function f(n,m:int64):int64;
begin
if n = 1 then f:= 1
else f:= ((n mod m)*(f(n-1,m) mod m)) mod m;
end;
可能会使用耗时的循环并乘以存储在字符串中的大量数字。此外，它适用于任何整数 m。
我找到此功能的链接：https ://www.quora.com/How-do-you-calculate-n-mod-m-where-n-is-in-the-1000s-and-m-is-一个非常大的素数-例如-n-1000-m-10-9+7
如果素数 m 的 n = (m - 1) 则由http://en.wikipedia.org/wiki/Wilson 's_theorem n! 模 m = (m - 1)
也正如已经指出的那样！如果 n > m，则 mod m = 0
假设您选择的平台的“mod”运算符足够快，那么您主要受计算速度n!和可用于计算的空间的限制。
那么它本质上是一个两步操作：
没有必要使事情复杂化，尤其是在速度是关键因素的情况下。通常，在循环内尽可能少地执行操作。
如果您需要n! mod m重复计算，那么您可能需要记住执行计算的函数的值。与往常一样，这是经典的空间/时间权衡，但查找表非常快。
最后，您可以将记忆与递归（如果需要，还可以使用蹦床）结合起来，让事情变得非常快。