n的阶乘末尾含有“0”的个数

关于这道题，见过两种问法：

1. 给定参数n（n为正整数），请计算n的阶乘n！末尾所含“0”的个数。
2. (n!%(10^k)) == 0。已知n，求能使上式成立的K的最大值。

问题分析：

显然，对于阶乘这个大数，我们不可能将其结果计算出来，在统计其末尾所含有的“0”的个数。所以必须从其数字特征进行分析。

首先考虑一般的情形。对于任意一个正整数，若对其进行因式分解，那么其末尾的“0”必可以分解为2*5。这里每一个“0”必然和一个“2”与“5”对应。这里是阶乘，含有2的分解比含有5的分解多很多。所以这道题的是问：正整数n因式分解中“5”的个数。例如6的阶乘：

6! = 6 * 5 * 4 * 3 * 2 * 1
分解后
6! = (3*2)*5*(2*2)*3*2*1 = 5*3*3*2*2*2*2*1
           

从上面的例子可以看出，分解之后6的阶乘含有一个5,四个2，2的个数5多很多。

对于n<5，因为不含分解因子“5”，所以末尾没有0。

但是对于n>=5的情况呢？我们可以把含有分解因子为“5”的给提出来，把n!变为

n! = [5m*5(m-1)*....*10*5]*a，a是一个不含因子“5”的整数，其中n = 5m + r （0<= r <= 4）
           

例如26的阶乘：

26! = [25*20*15*10*5]*26*24*23*22*21*19*......*1
26! = [(5*5)*(5*4)*(5*3)*(5*2)*5]*26*24*23*22*21*19*......*1 
26! = [(5*5)*(5*4)*(5*3)*(5*2)*5]*a（a代表后面所有数相乘）
           

通过上面的分解我们很容易看出26的阶乘一共有6个分解因子“5”。但是特别大的正整数呢？我们可不能手写出来然后数个数，所以我们还要进一步分析。

当 m>=5 时，m本身也可以分解出“5”，所以我们需要在原有的基础上再加m分解后的“5”的个数，现在n的阶乘可以写为：

n! = 5^m * m! * a
           

推导过程是：

n! = [5m*5(m-1)*....*10*5]*a = [5*5*5....*5*m*m-1*m-2*.....*1]*a 
整合之后得到
n! = 5^m * m! * a
           

通过上面的推导，我们可以得出最终的公式，令f(x)表示正整数x末尾所含有的“0”的个数, g(x)表示正整数x的因式分解中因子“5”的个数：

f(n!) = g(n!) = g(5^k * k! * a) = k + g(k!) = k + f(k!)

所以，最终的计算公式为：

当0 < n < 5时，f(n!) = 0;

当n >= 5时，f(n!) = k + f(k!), 其中 k = n / 5（取整）

到这里代码就写了，这不是递归调用嘛，所以代码写为：

int func(const int x)
{
	if ( x < 5)
	{
		return 0;
	}

	int y = x / 5;

	return y + func(y);
}
           

但是递归调用涉及到函数的调用开销，效率并不高，我们既然有公式了，可以直接带入公式：

int func2(int x)
{
	int y = 0;
	while (x > 4)
	{
		x = x / 5;
		y += x;
	}

	return y;
}
           

还有一种写法，我觉着比较难理解：

int func3(const int x)
{
	int y = 0;
	for (int i = 5; i <= x; i *= 5)
	{
		y += x / i;
	}
	return y;
}
           

感谢大家，我是假装很努力的YoungYangD（小羊）。

参考资料：

https://www.cnblogs.com/hutonm/p/5624996.html