题目背景
不告诉你……
题目描述
求出1!*2!*3!*4!*……*n!的末尾有几个零
输入输出格式
输入格式：
n(n<=10^8)
输出格式：
有几个零
输入输出样例
输入样例#1： 复制
10
输出样例#1： 复制
7
首先末尾有0肯定就是乘10，10可以分解为2和5，显然2的数目多于5，于是就是统计5的数目
然后可以转化一下，
对于
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
1 2 3 4 5 6
……
1 2 3 4 5 6 …… x
我们来除一下5，发现能被5整除的项变成了：
1
1
1
1
1
1 2
1 2
1 2
1 2
1 2
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
……
1 2 3 4 5 …… x/5
1 2 3 4 5 …… x/5
1 2 3 4 5 …… x/5
1 2 3 4 5 …… x/5
1 2 3 4 5 …… x/5
也就是5个
1
1 2
1 2 3
……
1 2 3 4 5 …… x/5
这样就可以递归求解了
另外，这次除5总共除掉了5+10+15+20+(n/5)*5个，可以用等差数列公式
对于x应该是从5k+4开始的，多余的处理掉即可 时间复杂度O(logn)
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
int n;
ll work(int x){
ll ret=;
for(int i=;i<=x;i*=){
ret+=x/i;
}
return ret;
}
ll find(int x){
if(x<){
return ;
}
if(x<){
return (x-);
}
ll ret=;
while((x+)%){
ret+=work(x);
x--;
}
ret+=1LL**(x/)*(+(x/))/;
ret+=*find(x/);
return ret;
}
int main()
{
scanf("%d",&n);
printf("%lld\n",find(n));
return ;
}