自动搬运

查看原文

来自洛谷，原作者为

	虞皓翔 Eternal dominant seventh.

搬运于2025-08-24 21:37:08，当前版本为作者最后更新于2017-02-14 20:00:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

居然发现没有人用$\Theta(\log n)$的算法，前面几楼都是$\Theta(n)$甚至更高，现在就来一发$\Theta(\log n)$的算法。

首先，令$f(n)=\sum_{i=1}^\infty\lfloor\frac n{5^i}\rfloor$，得到所求为

//怕latex太长显示出一堆em什么的东西

所以显然是$\Theta(\log n)$的。

核心代码：

for(j = 5; j <= n; j *= 5){
        ans += j * (n / j) * (n / j - 1) >> 1;
        ans += (n / j) * (n % j + 1);
    }