51Nod-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

问题链接：51Nod-1003 阶乘后面0的数量

问题分析：

这个问题是计算n！的后面有多少个0。因为2*5=10，那么0的个数依赖于其因子中的2的个数和5的个数。

2的个数自然比5的个数多很多，就只需要知道5的个数即可。

令f(x)表示正整数x末尾所含有的“0”的个数, g(x)表示正整数x的因式分解中因子“5”的个数，那么有f(n!) = g(n!) = g(5^k * k! * a) = k + g(k!) = k + f(k!)。

程序说明：程序中，编写了一个非递归程序来计算0的个数。也可以编写一个递归程序来计算。

题记：（略）

参考链接：（略）

AC的C++程序如下：

#include <iostream>

using namespace std;

inline int getlast0s(int n)
{
    int ans = 0;

    while(n) {
        ans += n / 5;
        n /= 5;
    }

    return ans;
}

int main()
{
    int n;

    cin >> n;

    cout << getlast0s(n) << endl;

    return 0;
}