如何计算大数阶乘的最后几个 非零 数字?

大体上,我的意思是像 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,我 知道 我在这个错误中犯了一个非常大的逻辑错误,我只是无法将手指放在上面!

最佳答案

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

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

  • 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 的正确因数数。第二个是如果 m10 的质数,那么 m * m^(4 * 10^(k-1) - 1) 就是 1 mod 10^k 。因此,您现在可以“除以”模 10^k,并计算出不涉及 2 或 5 的答案的每个因子的最后几项,然后计算出 0 的数量和剩余因子的数量您拥有的 2 或 5 个。

    这是一个重要的优化。如果你知道 f(n) mod 2^8 和 5^8,不难弄清楚 mod 10^8。但是它的值 mod 这两个可以减少到一个中等大小的查找表。较大的一个,您只需将其存储为最多 4*390625 的奇数 n,但其中的数量少于 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

    关于algorithm - 一个非常大的阶乘的最后一个非零数字,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/45224037/

    10-11 22:53
    查看更多