一个非常大的阶乘的最后一个非零数字
Last non-zero digits of a very large factorial
如何计算一个大数的阶乘的最后几位非零位？
总的来说，我的意思是像 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 的正确个数。第二个是如果 m 与 10 互质，则 m * m^(4 * 10^(k-1) - 1) 是 1 mod 10^k。所以你现在可以 "divide" mod 10^k，并找出不涉及 2 或 5 的答案的每个因素的最后几项，然后找出 0 的数量，以及您拥有的 2 或 5 的剩余因子数。
这是一个重要的优化。如果你知道 f(n) mod 2^8 和 5^8，那么不难算出 mod 10^8。但是它的值 mod 这两个可以减少到 mod 最大大小的查找 table。较大的你只需要将它存储为奇数 n 最多 4 * 390625，但其中少于 800k。 （那时你已经乘以不能被 5 mod 5^8 整除的事物组中的所有元素，并且该乘积是 1。然后模式重复。）如果你使用 4 字节整数，这是几 MB 的查找 table，可以很容易地预先计算。
我应该解释一下为什么这个技巧有效，因为它并不明显而且我错了几次。诀窍是与 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.
如何计算一个大数的阶乘的最后几位非零位？
总的来说，我的意思是像 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 的正确个数。第二个是如果 m 与 10 互质，则 m * m^(4 * 10^(k-1) - 1) 是 1 mod 10^k。所以你现在可以 "divide" mod 10^k，并找出不涉及 2 或 5 的答案的每个因素的最后几项，然后找出 0 的数量，以及您拥有的 2 或 5 的剩余因子数。
这是一个重要的优化。如果你知道 f(n) mod 2^8 和 5^8，那么不难算出 mod 10^8。但是它的值 mod 这两个可以减少到 mod 最大大小的查找 table。较大的你只需要将它存储为奇数 n 最多 4 * 390625，但其中少于 800k。 （那时你已经乘以不能被 5 mod 5^8 整除的事物组中的所有元素，并且该乘积是 1。然后模式重复。）如果你使用 4 字节整数，这是几 MB 的查找 table，可以很容易地预先计算。
我应该解释一下为什么这个技巧有效，因为它并不明显而且我错了几次。诀窍是与 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.