快速的方法来计算n！ mod m其中m是素数？
我很好奇，如果有一个好办法做到这一点。 我目前的代码是这样的：
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，并想知道这是否可以在这里以某种方式使用？
或者，我怎样才能创build一个recursion，memoized函数在C + +？
把我的评论扩展到一个答案：
是的，有更有效的方法来做到这一点。 但他们非常混乱。
所以除非你真的需要额外的performance，否则我不build议去实现这些。
关键是要注意模数（实质上是一个分数）将成为瓶颈操作。 幸运的是，有一些非常快速的algorithm可以让您在同一个数上多次执行模数。
- 用不变整数除法乘法
- 蒙哥马利减less
这些方法很快，因为它们实质上消除了模量。
单单这些方法应该会给你一个适度的加速。 为了真正有效率，您可能需要展开循环才能使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 ++。
n可以是任意大的
那么， n不能任意大 – 如果n >= m ，那么n! ≡ 0 (mod m) n! ≡ 0 (mod m) （因为m是factorial的定义之一） 。
假设n << m并且您需要一个确切的值，就我所知，您的algorithm无法得到更快的速度。 但是，如果n > m/2 ，则可以使用以下标识（ Wilson's定理 – 谢谢@Daniel Fischer！）
在大约mn限制乘法的次数
（M-1）！ ≡-1（mod m） 1 * 2 * 3 * ... *（n-1）* n *（n + 1）* ... *（m-2）*（m-1） N！ *（n + 1）* ... *（m-2）*（m-1）≡-1（mod m） N！ ≡ - [（n + 1）* ... *（m-2）*（m-1）] -1 （mod m）
这给了我们一个简单的方法来计算n! (mod m) n! (mod m)乘以mn-1 ，加上一个模逆 ：
def factorialMod（n，模数）：
ANS = 1
如果n <=模数// 2：
＃通常计算阶乘（范围（）的右参数是唯一的）
我在范围内（1，n + 1）：
ans =（ans * i）％模量
其他：
#Fancypants方法大n
我在范围内（n + 1，模数）：
ans =（ans * i）％模量
ans = modinv（ans，modulus）
ans = -1 * ans +模量
返回ans％模量
我们可以用另一种方式来重新说明上述方程式，可能会或可能不会稍快一点。 使用以下标识：
我们可以将方程改为
N！ ≡ - [（n + 1）* ... *（m-2）*（m-1）] -1 （mod m）
N！ ≡ - [（n + 1-m）* ... *（m-2-m）*（m-1-m）] -1 （mod m）
（相反的条款顺序）
N！ ≡ - [（ - 1）*（-2）* ... * - （mn-2）* - （mn-1）] -1 （mod m）
N！ ≡ - （（1）*（2）* ... *（mn-2）*（mn-1）*（-1） （mn-1） ] -1 （mod m）
N！ ≡[（mn-1）！] -1 *（-1） （mn） （mod m）
这可以用Python编写如下：
def factorialMod（n，模数）：
ANS = 1
如果n <=模数// 2：
＃通常计算阶乘（范围（）的右参数是唯一的）
我在范围内（1，n + 1）：
ans =（ans * i）％模量
其他：
#Fancypants方法大n
我在范围内（1，模数-n）：
ans =（ans * i）％模量
ans = modinv（ans，modulus）
＃因为m是一个奇素数，（-1）^（mn）= -1，如果n是偶数，则+1如果n是奇数
如果n％2 == 0：
ans = -1 * ans +模量
返回ans％模量
如果你不需要一个确切的值，生活变得更容易 – 你可以使用斯特林（Stirling）的近似来计算O(log n)时间的近似值（使用取平方的指数 ） 。
最后，我应该提到，如果这是时间关键的，而且您正在使用Python，请尝试切换到C ++。 从个人的经验来看，你应该期望速度提高一个数量级甚至更多，仅仅是因为这正是本机编译代码所擅长的那种CPU限制的紧缩循环（不论何种原因，GMP似乎比Python的Bignum精细得多） 。
N！ mod m可以用O（n 1/2 +ε ）运算来计算，而不是原始的O（n）。 这需要使用FFT多项式乘法，并且仅对于非常大的n是值得的，例如n> 10 4 。
该algorithm的概要和一些时间可以在这里看到： 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(ba) * polylog(ba) ) 。
为了简单起见，假定(b-a+1) = k^2是平方。 现在，我们可以把我们的产品分成k个部分，即M = [a*..*(a+k-1)] *...* [(b-k+1)*..*b] 。 这个产品中的每个因子都是p(x)=x*..*(x+k-1) ，对于适当的x 。
通过使用诸如Schönhage-Strassenalgorithm的多项式的快速乘法algorithm，以分而治之方式，可以p(x) in O( k * polylog(k) )find多项式p(x) in O( k * polylog(k) )的系数。 现在，显然有一个algorithmreplacek点在同一K度多项式在O( k * polylog(k) ) ，这意味着，我们可以计算p(a), p(a+k), ..., p(b-k+1)快。
这种将许多点代入一个多项式的algorithm在C.Pomerance和R.Crandall的书“Prime numbers”中描述。 最后，当你有这些k值时，你可以将它们乘以O(k)并得到所需的值。
请注意，我们所有的操作采取(mod p) 。 确切的运行时间是O(sqrt(ba) * log(ba)^2 * log(log(ba))) 。
扩展我的评论，这[100，100007]其中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
如果n =（m-1），那么可以通过http://en.wikipedia.org/wiki/Wilson的s_theorem n！ mod m =（m-1）
也正如已经指出的那样！ 如果n> m，mod m = 0
我在quora上find了这个函数：
用f（n，m）= n！ mod m;
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;
可能打败使用一个耗时的循环，并乘以存储在string中的大数字。 而且，它适用于任何整数m。
我find这个函数的链接： https : //www.quora.com/How-do-you-calculate-n-mod-m-where-n-is-in-the-1000s-and-m-is-一个-超大型素数-例如-正-1000-M-10-9 + 7
该algorithm具有O(n log log(n))预处理时间复杂度（由于筛选）和O（r（n））空间复杂度，其中r(n)是主要计数函数 。 预处理后，查询x！ 其中x <= N是O(r(x) * log(x)) 。
不幸的是，这对10 10是不可行的，因为r（1e9）是455,052,511，需要几乎2GB的内存来存储整数。 然而对于10 9 ，我们只需要大约300MB的内存。
假设mod是1e9 + 7来避免C ++的溢出，但它可以是任何东西。
一种计算N的方法！ mod m快
计算N！ 快，我们可以将N分解为它的主要因素。 可以观察到，如果p是N！的一个主要因素，那么p必须<= N，因为N！ 是从1到N的整数的乘积。鉴于这些事实，我们可以计算N！ 仅使用2到N（包含）之间的素数。 根据维基百科 ，有大约5,847,534（〜5 * 10 ^ 7）的素数小于或等于10 9 。 这将是使用的公式：
v p（N！）是使得p v p （N！）除以N！的最大数目。 Legendre的公式计算O（log（N））时间内的v p （N！）。 这里是维基百科的公式。
int factorial(int n) { int ans = 1; for (int i = 0; i < primes.size() && primes[i] <= n; i++) { int e = 0; for (int j = n; j > 0; ) { j /= primes[i]; e += j; } ans = ((u64) ans * fast_power(primes[i], e)) % mod; } return ans; }
fast_power(x, y)返回O（log（y））时间中的x y ％mod，使用平方指数 。
生成素数
我正在使用Eratosthenes筛生成素数。 在我的sieve的实现中，我使用bitset来节省内存。 当我使用第二代i3处理器编译-O3标志时，我的执行花费了16-18秒来产生高达10 ^ 9的素数。 我相信有更好的algorithm/实现来产生素数。
const int LIMIT = 1e9; bitset<LIMIT+1> sieve; vector<int> primes; void go_sieve() { primes.push_back(2); int i = 3; for (int i = 3; i * i <= LIMIT; i+=2) { if (!sieve.test(i)) { primes.push_back(i); for (int j = i * i; j <= LIMIT; j += i) { sieve.set(j); } } } while (i <= LIMIT) { if (!sieve.test(i)) primes.push_back(i); i+=2; } }
内存消耗
根据维基百科 ，有50,847,534素数小于或等于10 ^ 9。 由于32位整数是4个字节，因此主要向量需要203.39 MB（50,847,534 * 4个字节）。 筛子位需要（125 MB）10 ^ 9位。
性能
我能计算出10亿！ 在1.17秒后处理。
注意：我使用-O3标志启用了algorithm。
假设你select的平台的“mod”运算符足够快，那么你主要受限于你计算n!的速度n! 以及您可用于计算的空间。
那么这本质上是一个两步操作：
- 计算n！ （有很多快速algorithm，所以我不会在这里重复）
- 以结果的mod
没有必要使事情复杂化，特别是如果速度是关键的组成部分。 一般来说，尽可能less的循环内的操作。
如果你需要计算n! mod m n! mod m ，那么你可能想要记忆从函数进行计算的值。 与往常一样，这是经典的空间/时间折衷，但查找表非常快。
最后，你可以结合记忆和recursion（如果需要，也可以使用蹦床），以使事情真的很快。
