HDU 1124 Factorial 数学

缘起

就是n为正整数，问 n! 后面有几个0. 这道题本来是道面试题, 但是我还是想把这道题在oj上提交了. 这样的话, 给出的算法在时间和空间都有保障, 心安~ 遂找到了 HDU 1124 Factorial

分析

题目挺绕的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
GSM网络中最重要的部分是所谓的基站收发信台（BTS）。这些收发器形成称为单元的区域（这个术语将名称赋予蜂窝
电话），并且每个电话以最强的信号连接到BTS（在一点点简化视图中）。当然，BTS需要引起注意，技术人员需要定
期检查其功能。
ACM技术人员最近遇到了一个非常有趣的问题。鉴于要访问的一组BTS，他们需要找到访问所有给定点的最短路径并返
回中央公司大楼。程序员花了几个月的时间来研究这个问题，但没有结果。他们无法快速找到解决方案。很长一段时间后，其中一位程序员在一篇会议文章中发现了这个问题。不幸的是，他发现这个问题被称为“旅行推销员问题”而且很难
解决。如果我们要访问N个BTS，我们可以按任意顺序访问它们，给我们N！检查的可能性。表示该数字的函数称为阶
乘，可以作为乘积1.2.3.4 .... N计算。即使对于相对较小的N，该数字也非常高。

程序员明白他们没有机会解决问题。但由于他们已经从政府获得了研究经费，他们需要继续学习并至少产生一些结
果。所以他们开始研究阶乘函数的行为。

例如，它们定义了函数Z.对于任何正整数N，Z（N）是数字N！的十进制形式末尾的零数。他们注意到这个功能永远不
会减少。如果我们有两个数字N1 <N2，那么Z（N1）<= Z（N2）。这是因为我们永远不会通过乘以任何正数来“失
去”任何尾随零。我们只能得到新的和新的零。函数Z非常有趣，因此我们需要一个能够有效确定其价值的计算机程
序。

【输入】
第一行输入上有一个正整数T. 它代表要遵循的数字数量。 然后有T行，每行包含正整数N，1 <= N <= 
1000000000。

【输出】
对于每个数字N，输出包含单个非负整数Z（N）的单个行。

【样例输入】
6
3
60
100
1024
23456
8735373

【样例输出】
0
14
24
253
5861
2183837

【限制】
Time limit 1000 ms
Memory limit 32768 kB

注意到 10=2*5， 但是2的个数远没有5多，所以0的个数就是5的个数. 所以只需要统计5因子的个数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//#include "stdafx.h"
#include <stdio.h>

//#define LOCAL

int main()
{

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif   
	int t;
	scanf("%d", &t);

	while(t--)
	{
		int n ;
		scanf("%d", &n);
		int sum = 0;
		while(n)
		{
			sum+=(n=n/5);
		}
		printf("%d\n", sum);
	}
	return 0;
}

ac情况

Status Accepted
Time 93ms
Memory 1732kB
Length 293
Lang C++
Submitted 2019-08-08 10:35:13
Shared
RemoteRunId 30164211