链接:https://www.nowcoder.com/acm/contest/135/D
来源:牛客网
 

题目描述

输入描述:

输入数据共一行,一个正整数n,意义如“问题描述”。

输出描述:

输出一行描述答案:

一个正整数k,表示S的末尾有k个0

示例1

输入

复制

10

输出

复制

7

说明


 

求末尾有多少个0即计算乘积中有多少个5*2,所以只需要计算有多少个5相乘即可

因为n的数据范围很大,直接for循环,然后求每一个数阶乘中有多少个5的话一定会超时。

需要注意到的是,5!6!7!8!9!这些数的阶乘中5的个数是相同的。

 方法1:运行时间 196ms

n!与(n+1)!之间只相差n+1,所以只需要计算n+1中有多少个5相乘,再加上n!中5的个数

ac代码:

#include<bits/stdc++.h>
using namespace std;
long long n,ans=0,te=0;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        int k=i;
        while(k%5==0)
        {
            te++;
            k/=5;
        }
        ans+=te; 
    }
   printf("%lld\n",ans);
    return 0;
}

方法2:  运行时间:3ms

我们知道计算n!(比如n=133)中有几个质因数5的思路是:

1、133/5=26;说明133的阶乘中有26个数是5的倍数

2、133/25=5,说明133的阶乘中有5个数是25的倍数

2、133/125=1,说明133的阶乘中有1个数是125的倍数

那么133阶乘中质因数5的个数则是26+5+1

同理,按照同样的思路,先计算133!~1!这些阶乘中每个阶乘中有几个数是5的倍数、25的倍数、125的倍数,最后相加即可。

以上图为例,k=133/5=26,五个为一组,那么这些阶乘中有(k-1)(k-1+1)/2*5+(n%5+1)*k个数是5的倍数(第一部分的求和用到了求和公式n(a1+an)/2

再令k=133/25.......k=133/125计算即可得出最终答案

ac代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll n,i,j,k,ans=0;
    scanf("%lld",&n);
    for(i=5;i<=n;i*=5)
    {
        ll sum=0;
        k=n/i;
        sum=k*(k-1)/2*i;
        sum+=k*(n%i+1);
        ans+=sum;
    }
    printf("%lld\n",ans);
}

在网上百度了好久找到的都是第一种解题思路,但是我在看大佬们提交代码的时候发现了第二种方法,很明显,相比于第一种方法来说,第二种超省时,而且代码量也很少。读者根据个人喜好选择哪种解题方法哦

欢迎讨论,非诚勿扰哦~邮箱:1308989543@qq.com