自动搬运

查看原文

来自洛谷，原作者为

	WinXP **

搬运于2025-08-24 21:38:43，当前版本为作者最后更新于2018-05-08 14:46:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

说真的 大佬的题解真的太意识流了(两篇) 对蒟蒻来说能坚持到看明白需要勇气啊。。对蒟蒻真的是不友善。。 或许怎么说。。。 这就是大佬吧。

首先公式给出，与那位大佬V2.0版中的公式相同。设 $f(x)$ 表示 $x!$ 最后一个非0的数，那么有

$$f(x)=f(x/5)×a(x \% 20)$$

$a$ 是预设的数组。

首先嘛 不要考虑 $10^{100}$ 这么大的数。来考虑一些友善的数据范围，比如 $100000$ 这么大之类的。这个怎么做呢？

如果求某一个数 $x$ 的最后一位那谁都会：$x\%10$。如果求的是某一个数 $x$ 的最后一位非0的数，在 $x/10$ 能算的出来的时候，$while(x\%10==0) x/10$ 再 $\%10$ 就好了。

注意这两点：$x×y\%10=(x\%10)×(y\%10)$。 $10$ 等于 $2×5$ 并且 $2,5$ 都是质数。

那么现在把 $x!$ 表示为 $c×2^{a}×5^{b}$。( $c$ 不包含质因子 $2$ 和 $5$ ) 显然 $a>b$ 。(这里显然没问题吧) 所以最后的结果应该为 $2^{a-b}×c\%10$。

想到这里我们就可以用约为 $O(n)$ 级别的时间来计算这个解了。初始化 $ans=1$ ，对于从 $1$ 到 $x$ 的每一个数，都除尽它的 $2$ 因子与 $5$ 因子，记下 $a-b$ 的值，除干净了把这个数 $\%10$ 并乘上 $ans$ ，最后 $ans$ 乘一下 $(a-b)$ 个 $2$ ，就能得到结果。

我们显然可以优化这个过程。

先把所有的 $5$ 的倍数都拿出来放到一边，一会乘起来。原数组会变成类似

$$1,2,3,4,1,6,7,8,9,1,11,12,13,14,1,16,17,18,19,1,21,22 ... $$

这样。

考虑像分块一样把每 $10$ 个数作为一组。假想我们有一种方式，能将几个数相乘后的结果中的 $10$ 预先抽离出来，将它变成

$$(1×2×3×4×1×6×7×8×9×1\%10+10×q_1)$$ $$×$$ $$(1×2×3×4×1×6×7×8×9×1\%10+10×q_2)$$ $$×$$ $$...........$$ $$×$$ $$(1×2×3×4×1×6×7×8×9×1\%10+10×q_n)$$

这个样子。

很显然如果不提 $2$ ，每一段乘起来 $\%10$ 的值都是相同的 $6$ 。

当然提 $2$ 之后也是相同的。每 $10$ 个数，拿走两个 $2$ 来和提取出的两个 $5$ 的倍数值进行匹配，无论 $q_i$ 的值如何(即使是 $0$ )，每组 $\%10$ 后的值都将变成 $4$ 。

现在就变成了，很多个 $4$ 乘起来，乘最后没完整划分为 $10$ 个数的那一组，乘上一堆之前提出的 $5$ 的倍数再 $/5$ 的值，的最后一位非 $0$ 值是多少。什么是"一堆之前提出的 $5$ 的倍数再 $/5$ 的值"? 就是说提出的 $5,10,15,20,25,30...$ 这些数，每一个 $/5$ ，提出的 $5$ 与提出的 $2$ 乘在一起变成 $10$ 扔掉，就变成了 $1×2×3×4×5×6×....$

这一共有 $x/5$ 个数。也就是

$4^{?}×$最后的那几个分不了组的数$× f(x/5)$

$4×4\%10=6$ 。聪明的你会发现，对于 $x!$ 的最后一个非 $0$ 数，一定是偶数，换句话说就是 $2,4,6,8$ 中的一个。

$6*2\%10=2$，$6*4\%10=4$，$6*6\%10=6$，$6*8\%10=8$。 $6$ 与能成为答案的数相乘都是不改变值的所以我们干脆每20个数分成一组，每一组为原来的两组，提出 $2$ 和 $5$ 之后的值是 $6$ 。 $6$ 与任何一个答案值乘在一起是不会变的，所以我们可以当做没看见。

对于最后面的几个数显然是可以预处理的。所以现在答案变成了 $6^{?}×$ 预处理 $× f(x/5)=$ 预处理 $× f(x/5)$

把预处理的数组放到 $a$ 上面就好了。

也就是说如果你理解了的话，$a$ 数组是

$$1,2,3,4,\frac{1}{2},6,7,8,9,\frac{1}{2}....$$

的前缀和。不对，前缀乘（ $\%10$ ）。

所以代码几乎是只要维护一个区区 $100$ 位的高精除。复杂度 $O(n^2log_510)$ 。我写的太丑，就不放了。