d122 - Oh! My Zero!!

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算一個給定數字 n 的階乘 n! 末尾有多少個零。

解題思路

計算 n! 末尾零的個數，實際上是計算 n! 中有多少個 5 的因數。因為 2 的因數數量總是比 5 的因數數量多，所以只需要計算 5 的因數數量即可。 程式碼使用貪心策略，不斷地將 n 減去它除以 5 的餘數，然後除以 5，直到 n 小於等於 4。每次除以 5 的結果累加到 a 中，a 就是末尾零的個數。

複雜度分析

• 時間複雜度: O(log5(n))
• 空間複雜度: O(1)

程式碼

#include <stdio.h>
int main(){ 
	long int n;
	int a=0;
	while(scanf("%ld",&n)>0){
		while(n>4){
			n-=n%5;
			a+=n/5;
			n/=5;
		}
	printf("%d\n",a);
	a=0;
	}
}