P2388第一篇题解——附加解释

· · 个人记录

题解原文 # 显然因为作者太巨，没有去解释清，导致我这样的蒟蒻一开始没看明白，所以在这里做附加解释。

但只会详细说最后一步展开，前面的

f(n)=\sum_{i = 1}^{\lfloor{log_5 n}\rfloor} \lfloor{\frac{n}{5^i}}\rfloor

的原理具体去看 P10495 的题解\ (此处把 \infin 转化为 \lfloor{log_5 n}\rfloor 效果是一样的)

对于最后一步的展开，首先我们要想到 n! 的质因数中 5 的个数必然存在关系

num(n) \le num(n+1)

那么如果有 a，b满足

num(a)=num(b)+1

即可以知道 a 和 b之间存在一个 5 的倍数，或者这样表达：

a \in [5i,5(i+1)-1]\\ b \in [5(i+1),5(i+2)-1]

那么我们可以推出当 a，b满足

num(a)+t=num(b)，t \in N^*

有

a \in [5i,5(i+1)-1]\\ b \in [5(i+t),5(i+t+1)-1]

这里我们就认为 b 在拥有 5^j 的个数上比 a 多一层，而：

5^j\sum_{i=1}^{\lfloor{\frac{n}{5^j}}\rfloor-1}{i}

便表达了——把所有含 5^j 个 5^j 的层数，的数字个数一层一层加起来（上一层比下一层少 5^j 个 5^j ）\ 可看 在第一行中，上式计算了5! 到 9! 中 5 的个数\ 在第二行中，上式计算了5! 到 14! 中 5 的个数\ 在第三行中，上式计算了5! 到 14! 中 5 的个数

这样我们便可以发现在第二行中上式计算展开为 (1+2)*5 \ 刚刚好就是把 5 的个数一层一层加起来，且每一层比前一层多 5 个 5。

如此之后，我们便可以看出，另一部分

\lfloor{\frac{n}{5^j}}\rfloor \cdot (n \bmod {5^j}+1)

计算的就是，剩下的，在一层中，不足 5^j 个，但含 5^j 的个数。\ 如图中第三行 15! 到 17! 中每一个都有 3 个 5 ，总共 9 个 5 ，

\lfloor{\frac{n}{5^j}}\rfloor

这个式子便得到每个数字含 5^j 的个数，对于例子中第三行来说就是 3 个 5 的意思

(n \bmod {5^j}+1)

这个式子便得到了 在一层中，不足 5^j 个 的数字个数，对于例子中第三行来说就是有 3 个数字满足条件，即 15，16，17。

所以综合起来

{5^j\sum_{i=1}^{\lfloor{\frac{n}{5^j}}\rfloor-1}{i}}+{\lfloor{\frac{n}{5^j}}\rfloor \cdot (n \bmod {5^j}+1)}

表达的就是 5^j 在 \prod_{i=1}^{n}{i!} 中的个数\ 最后全部加起来（即\sum_{j=1}^{log_5 n}）就是答案 ans(n)

再自说自话地解释一下

ans += j * (n / j) * (n / j - 1) >> 1;

后面这一部分就是使用了等差数列求和公式，写下来就是：

\frac{\lfloor\frac{n}{j}\rfloor(\lfloor\frac{n}{j}\rfloor-1)}{2}

刚好就是首项加末项 乘 项数 除 2 # 以上为个人研究结果，若有问题请各位dalao指正

膜拜原题解作者 @虞皓翔