algorithm - 一个非常大的阶乘的最后一个非零数字

Question

如何计算大数阶乘的最后几位非零数字？

总的来说，我的意思是像 n=10^100 之类的
(编辑:10^100 是 n 中“n”的大小!)
很少，我的意思是直到 7-8 点......

我试着用谷歌搜索它并找到了这个 -

Last non-zero digit of a factorial

我试图将其扩展到最后 2 个非零数字或更多，但失败了...

我在 google 上找到了其他显示如何计算最后 x 位数的网站，但不清楚，我也无法理解...

谁能帮我解决这个问题？

此外，我无法得到这个，99 的最后两个非零数字!是 64，所以我认为(199!/99!)的最后两个非零数字也应该是 64，但结果是 24，我知道我正在制作一个非常大的这一个中的逻辑错误，我只是无法指责它!

Answer 1

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

1. 答案中 5 的因数个数。
2. 答案中 2 的因数个数。
3. 答案中所有其他素数的所有乘积的最后几位数字。

5 的因数个数就是 10 的因数个数。然后从 5 的因数个数中减去 2 的因数个数。计算出 2 的最后几位数字的次方。将其乘以在第 3 步中找到的最后几位数字，就完成了。

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

2的因数的个数可以类似地用数列2、4、8、16代替。

第三部分比较棘手。

但更容易做的是找出所有数字的乘积，直到并包括 n，它们与 2 和 5 互质。调用该函数 f(n )。您可以通过将相对质数乘以 mod 10^k 来计算它。并利用 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如何做到这一点。对于 10^100，这个序列中仍然只有数万个 - 它在控制之中。

---

关于比率的第二个问题，您需要利用以下两个事实。事实 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 mod 5^8 整除的事物组的所有元素，并且该产品是 1。然后模式重复。)如果你使用 4 字节整数，那是几 MB 查找可以很容易地预先计算的表格。

我可能应该解释为什么这个技巧有效，因为它并不明显而且我错了几次。诀窍是与 5^k 相对质数的数字形成一个组。意思是每个都有一个逆。所以如果你把它们全部相乘，然后重新排列，除了 5^k-1 之外，每个都有一个倒数。因此，乘以另一个副本，它们再次配对，包括那个讨厌的副本，结果为 1。现在对于我们的 f，我们只对不能被 5 整除的奇数感兴趣，但奇数不能被 5 整除到 2* 5^k 是 mod 5^k，只是将可被 5 整除的值重新排列为 5^k。我们需要 2 个副本，因此需要 4*5^k。但我们只需要赔率，因为紧随其后的偶数始终与前一个奇数具有相同的值。

---

根据请求，以下是单个示例的工作原理。我会做 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。