非常大阶乘的最后非零位

计算的诀窍是要找到3个数字。

2. 答案中2的因子数。

因子数5等于因子数10。然后从因子数5中减去因子数2。计算出2的最后几个数字的幂。将其乘以步骤3中找到的最后几个数字,就完成了。

5的因子数可以计算如下。取n/5(四舍五入)。这就是第一个因子为5的数量。然后n/25(四舍五入)。第二个因子是5。继续,直到完成。

只有用序列2、4、8、16代替,才能类似地计算出2的因子数。

n 2和5的相对素数。调用该函数 f(n) f(i * 10^k + j) = f(j) mod(10^k) .

f(n)*f(n/2)*f(n/4)*f(n/5)*f(n/8)*f(n/10)*f(n/16)*... .高效地生成该序列是汉明数问题的一个版本。看见 https://rosettacode.org/wiki/Hamming_numbers

关于比率的第二个问题,您需要利用以下两个事实。事实1是你只需要通过减法就知道2和5的正确因子数。第二个是如果 m 相对而言 10 m * m^(4 * 10^(k-1) - 1) 是 1 mod 10^k 所以你现在可以“除以”mod 10^k,算出答案中不包含2或5的每个因子的最后几项,然后算出0的数量,以及剩下的2或5的因子的数量。

这是一个重要的优化。如果你知道 f(n) mod 2^8和5^8,不难计算出mod 10^8。但它的值mod这两个可以减少到一个中等大小的查找表。较大的一个只需要存储奇数n到4*390625的数据,但不到800k。(此时,你已经将不可被5除以5的所有元素相乘,乘积为1。然后模式重复。)如果你使用4字节整数,那么这就是可以相当容易地预先计算的几MB查找表。

我可能应该解释一下为什么这个伎俩有效,因为它并不明显,而且我有几次搞错了。诀窍是,相对素数为5^k的数字组成一个群。意思是每一个都有一个反比。如果你把它们全部乘出来,重新排列,每个都有一个倒数,除了5^k-1。再乘以另一个副本,它们再次配对,包括那个讨厌的副本,乘积为1。现在对于我们的f,我们只关心不可被5整除的奇数,但不可被5整除到2*5^k的奇数,mod 5^k,只是可被5整除到5^k的奇数的重新排列。我们需要2份复印件,因此需要4*5K。但我们只需要赔率,因为后面的偶数总是与前面的奇数具有相同的值。

根据请求,下面是一个示例的工作原理。我会做15的最后3位!

15! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15
    = (1*3*7*9*11*13) * (2*6*14) * (4*12) * (5*15) * (8) * (10)
    = (1*3*7*9*11*13) * 2^3*(1*3*7) * 2^4*(1*3) * 5^2*(1*3) * 2^3*(1) * 10*(1)
    = 2^11 * 5^3 * f(15) * f(15/2) * f(15/4) * f(15/5) * f(15/8) * f(15/10)
    = 2^11 * 5^3 * f(15) * f(15/2) * f(15/4) * f(15/5) * f(15/8) * f(15/10)
    = 10^3 * 2^8 * f(15) * f(7) * f(3) * f(3) * f(1) * f(1)
    Which leads to the calculation...
             256 *   27  *  21  *   3  *   3  *   1  *   1 (mod 1000)
                                                     = 368 (mod 1000)

这是正确的,因为 15! = 1307674368000 .