洛谷P2388 阶乘之乘 题解

题目链接：P2388 阶乘之乘

题意：

求出 $1!\times 2!\times 3!\times 4!\times \cdots \times n!$ 的末尾有几个零。

输入格式：

一行，一个整数 $n(n\le 10^8)$。

输出格式：

输出答案，表示零的个数。

很经典的一道题，先说一下 $\mathcal{O}(n)$ 的小学生解法：

注意到 $n!$ 中 $5$ 的个数显然小于 $2^i$ 的个数，于是我们只需要统计每个阶乘里有多少个 $5$​ 即可

scanf("%lld",&n);
for(int i=1; i<=n; i++)
{
    int tmp=i;
    while(tmp%5==0)sum++,tmp/=5;
    ans+=sum;
}
printf("%lld\n",ans); // 本代码写于 2021-03-08

下面说一下更快的解法。考虑把刚才的结论写成式子。

令 $f(n)=\sum_{i=1}^{\infty}\left\lfloor\frac{n}{5^i}\right\rfloor$ ，则

$$\mathrm{Ans}(n) = \sum_{i=1}^n f(i)=\sum_{i=1}^n \sum_{j=1}^{\infty}\left\lfloor\frac{i}{5^j}\right\rfloor=\sum_{j=1}^{\infty} \sum_{i=1}^n\left\lfloor\frac{i}{5^j}\right\rfloor=\sum_{j=1}^{\infty}\left(5^j \sum_{i=1}^{\left\lfloor\frac{n}{5^j}\right\rfloor-1} i+\left\lfloor\frac{n}{5^j}\right\rfloor \cdot\left(n \bmod 5^j+1\right)\right)$$

时间复杂度 $\mathcal{O}(\log n)$

主要代码：

int n, res = 0; cin >> n;
for(int j = 5; j <= n; j *= 5)
{
    res += j * (n / j) * (n / j - 1) / 2;
    res += (n / j) * (n % j + 1);
}
cout << res << '\n';

---

参考文献：

[1] https://www.luogu.com.cn/article/mqej6cz0