我有 N 个数字，我想计算阶乘模数 m 的总和
例如
4 100
12 18 2 11
Ans = (12! + 18! +2!+11!)%100
自 1<N<10^5和数字来自 1<Ni<10^17
如何在有效时间内计算它。
由于递归方法会失败，即
int fact(int n){
if(n==1) return 1;
return n*fact(n-1)%m;
}
最佳答案
如果您预先计算阶乘，使用每个操作 %m，并且将使用关于大于 m 的数字的阶乘评论中的提示，您将得到类似这样的结果
fact = new int[m];
f = fact[0] = 1;
for(int i = 1; i < m; i++)
{
f = (f * i) % m;
fact[i] = f;
}
sum = 0
for each (n in numbers)
{
if (n < m)
{
sum = (sum + fact[n]) % m
}
}
我不确定它是否最好，但它应该会在合理的时间内发挥作用。
Upd:可以使用以下知识优化代码:如果对于某个数字 j，(j!)%m ==0 比对于每个 n > j (n!)%m ==0 ，所以在某些情况下(通常是m 不是质数)没有必要为所有小于 m 的数预先计算阶乘
关于algorithm - 在最佳时间计算一个数的阶乘，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28366224/