51 nod 1003 阶乘后面0的数量

1003 阶乘后面0的数量

基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题

收藏

关注

取消关注

n的阶乘后面有多少个0？

6的阶乘 = 1*2*3*4*5*6 = 720，720后面有1个0。

 

Input

一个数N(1 <= N <= 10^9)

Output

输出0的数量

Input示例

5

Output示例

1

首先因为n很大，暴力不可解。然后分析下可知阶乘后面的0是由1~n中的5与2相乘得来的，而显然2的数量远远多于5，所以转换成求n的阶乘中有多少个5.
每5个数中会有1个数是5的倍数，在这些5的倍数的数中每5个数中有一个是25的倍数，依次类推。所以n/5=至少能提供一个因子5的数的数量，n/（5^2)=至少能提供2个因子5的数的数量……
因此用n不断的除以5，并把值累加起来就是答案。

#include <iostream>
using namespace std;
int main()
{
    int n;
    int ans=0;
    cin>>n;
    while(n)
    {
        ans+=n/5;
        n/=5;
    }
    cout<<ans<<endl;
    return 0;
}