快速算法计算大n!mod 2 ^ 32

Question

N最高可达2 ^ 31.我想计算N的准确值!mod 2 ^ 32.任何语言都可以,但我希望详细解释算法.时间限制<1秒

Answer 1

在python中:

if n > 33:
  return 0
else
  return reduce(lambda x, y: x*y, range(1, n+1)) % 2**32

理由:

我们知道34!可以被2 ³²整除,因为在序列中:

1 * 2 * 3 * 4 * ... * 34

有:

17 multiples of 2
 8 multiples of 4
 4 multiples of 8
 2 multiples of 16
 1 multiple  of 32
--
32 multiplications by 2

它是每个较大因子的一个因子,因此所有较大的因子都是0 mod 2 ³²

对于小的N值,如果你没有可用的bignum算法,你可以进行单独的乘法mod 2 ³²,和/或你可以在factorial中预先计算2的幂,这很容易计算(见上文).

Answer 2

正常计算阶乘(乘以数字1,2,3,...),在每次乘法后执行模数.这将为您提供小值的结果N.

对于较大的值N,请执行相同的操作.很快,您的中间结果将是0,然后您可以立即停止循环并返回0.您停止的点将相对较快:因为N == 64结果将是0因为1..64包含32个偶数的乘积因此可被整除2^32.N得到0 的实际最小值将小于64.