algorithm - 找到与 N 互质的某个数的修正阶乘 N

Question

给定两个数N和，p让是除以k的最大幂。互质数也是如此。pp^kN!d = N!/(p^k)dp

我如何找到d mod p？直接迭代将是不切实际的，因为N!在高时会非常N高。需要更有效的算法来找到表达式。

Answer 1

这是 O(N) 算法：

int d=1;
for(int i=1;i<=N;++i)
{
    d*=i;
    while(d%p==0)
      d/=p;
    d=d%p;
}

它不需要存储大量数字，因此可能是可以接受的。我怀疑 O(p) 算法是可能的（因为数字会在每个 k*p 之后重复），但是代码会更复杂一些。