题目描述
输入描述:
输入数据共一行，一个正整数n，意义如“问题描述”。
输出描述:
输出一行描述答案：
一个正整数k，表示S的末尾有k个0
输入例子:
10
输出例子:
7
-->
输入
10
输出
7
说明
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
int n,num,tmp;LL sum;
while(~scanf("%d",&n)){
sum=,num=;//num一开始置0，以后每次累加每个元素包含因子为5的个数即可
for(int i=;i<=n;++i){//从1枚举到n
tmp=i;//表示当前i!=(i-1)!*i
while(tmp%==)num++,tmp/=;//num累加当前i元素包含因子为5的个数
sum+=num;//累加i！尾数为0的个数
}
printf("%lld\n",sum);
}
return ;
}
AC代码二（78ms）：根据法一：求N！尾数有多少个0只需求N内为5的倍数的数包含因子为5的个数总和即可，而此题是求1~n内每个数的阶乘相乘之后尾数为0的个数，因此我们同样枚举N内所有为5的倍数i，每求出i包含因子为5的个数num后，因为i~n(n-i+1个元素)内每个数的阶乘都包含当前i这个元素，所以sum累加num*(n-i+1)即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
LL n,tmp,num,sum;
while(~scanf("%lld",&n)){
sum=;
for(LL i=;i<=n;i+=){
tmp=i;num=;
while(tmp%==)num++,tmp/=;
sum+=num*(n-i+);
}
printf("%lld\n",sum);
}
return ;
}
AC代码三（5ms）：如果测试数据真的很大为10^9，那么前两个肯定是超时的。因此能否根据法二同样用O(log5n)的时间复杂度计算出尾数为0的个数？根据法二公式：假设我们要计算1！~126！，即n=126，则①126/5=25，说明126！中有25个数是5的倍数；②126/25=5，说明126！中有5个数是25的倍数；③126/125=1，说明126！中有1个数是125的倍数。现对1！~126！按包含因子为5的个数（个数相同为同一组）从小到大分成k=n/i=126/5=25组：（共有k-1组每一组有都有5i(i=1,2,3...)个数的阶乘包含因子为5的个数是相同的，最后一组有（1+n%i）个元素）
j=1--->{5！，6！，7！，8！，9！}；//有i=5个元素每个元素包含1个因子5
j=2--->{10！，11！，12！，13！，14！}；//有i=5个元素每个元素包含2个因子5
...
j=24-->{120！，121！，122！，123！，124！}；//有i=5个元素每个元素包含24个因子5
j=25-->{125！，126！}//有2(1+n%i=1+126%5=1+1=2)个元素每个元素包含25个因子5
以上分组是i=5的情况，其他i值基本和这个一样：由等差数列求和公式可求得1！*...*126！中一共有x=(1+k-1)(k-1)/2*i+k*(1+n%i)（其中k=n/i,i=51,52,53...）个因子5，之后按此公式累加（因子为5的个数）x的值（sum+=x）即可求出1！*...*n！尾数为0的个数sum。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
LL n,sum;
while(~scanf("%lld",&n)){
sum=;
for(LL i=;i<=n;i*=){
LL k=n/i;
sum+=k*(k-)/*i+k*(+n%i);
}
printf("%lld\n",sum);
}
return ;
}