3

我想计算N的确切值！模 2 32。N 最大为 2 31

任何语言都可以，但我希望能详细解释算法。时间限制 < 1 秒

4

5 回答 5

21

在蟒蛇中：

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

理由：

我们知道34！可被 2 32整除，因为在序列中：

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 32

对于较小的 N 值，如果您没有可用的 bignum 算术，您可以进行单独的乘法 mod 2 32，和/或您可以在阶乘中预先考虑 2 的幂，这很容易计算（见上文）。

于 2013-03-05T17:44:26.717 回答
6

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

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

于 2013-03-05T17:43:38.123 回答
0

当乘以 2 个任意长度的数字时，低位总是准确的，因为它不依赖于高位。基本上a×b mod m = [(a mod m)×(b mod m)] mod m所以要做N！mod m只是做

1×2×...×N mod m = (...(((1×2 mod m)×3 mod m)×4 mod m)...)×N mod m

Modulo 2 n是一种特殊情况，因为通过操作获得模数相当容易AND。模 2 32更加特殊，因为 C 和大多数类 C 语言中的所有无符号运算都减少了 32 位无符号类型的模 2 32

因此，您只需将数字乘以两倍宽的类型，然后再乘以AND2 32 - 1 即可获得模数

uint64_t p = 1;
for (uint32_t i = 1; i <= n; i++)
    p = p*i & 0xFFFFFFFFU;
return p;
于 2013-08-18T00:58:52.843 回答
0

通常，您可以使用大多数编程语言中可用的整数类型（int、long）来实现算法以 2 的小幂为模，而无需使用 bignums 或模约简。对于模 2 32，您将使用 32 位整数。“整数溢出”负责模运算。

在这种情况下，由于只有 34 个不同的结果，因此查找表可能比计算阶乘更快，假设阶乘的使用频率足够高，以至于表被加载到 CPU 缓存中。执行时间将以微秒为单位。

于 2013-03-05T20:52:55.600 回答
-1

计算模是一种非常快速的运算，尤其是 2 的幂的模。相比之下，乘法的成本非常高。

最快的算法会分解质数中的阶乘因子（由于数字小于 33，所以速度非常快）。并通过将它们全部相乘，通过在每个乘法之间取模，并从大数开始来获得结果。

例如：计算 10！mod 2 32 : 使用 de Polignac 公式，得到 10 的质因数！这给了你：

10！= 7 * 5 * 5 * 3 * 3 * 3 * 3 * 2 ...

这将比基本算法更快，因为计算 (29! mod 2 32 ) X 30 比乘以 5、3 和 2 并在每次之间取模要困难得多。

于 2013-03-05T20:05:50.793 回答