题解 P2388 【阶乘之乘】

虞皓翔 · 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);
    }