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