md CF 要开始了写不了了
简要题意
求 \(1!\times 2!\times \cdots\times n!\) 的末尾有几个 \(0\) .
\(n\le 10^8\)
题解
主要思路
首先，一个数末尾有几个零等价于它有多少个因子 \(10\) .
即这个数有多少个因子 \(2\) 和 \(5\)，又因为因子 \(5\) 的数量少于因子 \(2\) 的数量，所以只需统计因子 \(5\) 的数量 .
注意，\(25\) 有两个 \(5\) 因子（笑）
一个 \(o(n)\) 的算法
这里确实是小写 \(o\)！！表示下界！其实只是因为我不会算这个时间复杂度233
就是平凡的去除因子 \(5\) 即可 .
一个 \(O(\log n)\) 的算法
这里讲的通俗一些 .
枚举 \(5\) 的方幂 \(5^k\) .
对于每个 \(i\) 计算 \(i!\) 的贡献，显然是 \(\left\lfloor\dfrac{i}{5^k}\right\rfloor\) .
那个下取整是 \(1,2,3,\cdots\) 重复 \(5^k\) 次的结果，用个等差数列求和就可解决！！
一个算法
其实这个题在 OEIS 上式能搜到的：http://oeis.org/A173345
但是我没找到 \(O(1)\) 公式 /xk
代码
算法 \(1\)（\(o(n)\)）
// 初始 t=0, s=0, ans=0
for (int i=1;i<=n;i++)
{
t=i;
while (!(t%5)){++s; t/=5;}
ans+=s;
}
算法 \(2\)
// 初始 now=5, ans=0
while (now<=n)
{
ll t=n;
while (t%now!=now-1){ans+=t/now; --t;}
ans+=now*(t/now)*(t/now+1)/2;
now*=5;
}