简要题意
求 (1! imes 2! imes cdots imes n!) 的末尾有几个 (0) .
(nle 10^8)
题解
主要思路
首先，一个数末尾有几个零等价于它有多少个因子 (10) .
即这个数有多少个因子 (2) 和 (5)，又因为因子 (5) 的数量少于因子 (2) 的数量，所以只需统计因子 (5) 的数量 .
注意，(25) 有两个 (5) 因子（笑）
一个 (omega(n)) 的算法
平凡的去除因子 (5) 即可 .
一个 (O(log n)) 的算法
这里讲的通俗一些 .
枚举 (5) 的方幂 (5^k) .
对于每个 (i) 计算 (i!) 的贡献，显然是 (leftlfloordfrac{i}{5^k} ight floor) .
那个下取整是 (1,2,3,cdots) 重复 (5^k) 次的结果，用个等差数列求和就可解决！！
一个算法
其实这个题在 OEIS 上式能搜到的：http://oeis.org/A173345
但是我没找到 (O(1)) 公式 /xk
代码
算法 (1)（(omega(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;
}