【題目描述】
Write an algorithm which computes the number of trailing zeros in n factorial.
設(shè)計(jì)一個(gè)算法望忆，計(jì)算出n階乘中尾部零的個(gè)數(shù)瓶盛。
【題目鏈接】
http://www.lintcode.com/en/problem/trailing-zeros/
【題目解析】
傳統(tǒng)解法是首先求出n!，然后計(jì)算末尾0的個(gè)數(shù)。（重復(fù)÷10喧笔，直到余數(shù)非0）該解法在輸入的數(shù)字稍大時(shí)就會(huì)導(dǎo)致階乘得數(shù)溢出，不足取迷殿。
O（logn）解法：一個(gè)更聰明的解法是考慮n!的質(zhì)數(shù)因子乱顾。后綴0總是由質(zhì)因子2和質(zhì)因子5相乘得來的。如果我們可以計(jì)數(shù)2和5的個(gè)數(shù)绪妹，問題就解決了甥桂。考慮下面的例子：
n = 5: 5!的質(zhì)因子中 (2 * 2 * 2 * 3 * 5)包含一個(gè)5和三個(gè)2邮旷。因而后綴0的個(gè)數(shù)是1黄选。
n = 11: 11!的質(zhì)因子中(2^8 * 3^4 * 5^2 * 7)包含兩個(gè)5和三個(gè)2。于是后綴0的個(gè)數(shù)就是2婶肩。
我們很容易觀察到質(zhì)因子中2的個(gè)數(shù)總是大于等于5的個(gè)數(shù)办陷。因此只要計(jì)數(shù)5的個(gè)數(shù)就可以了。那么怎樣計(jì)算n!的質(zhì)因子中所有5的個(gè)數(shù)呢律歼？一個(gè)簡單的方法是計(jì)算floor(n/5)懂诗。例如，7!有一個(gè)5苗膝，10!有兩個(gè)5殃恒。除此之外，還有一件事情要考慮辱揭。諸如25离唐，125之類的數(shù)字有不止一個(gè)5。例如问窃，如果我們考慮28!亥鬓，我們得到一個(gè)額外的5，并且0的總數(shù)變成了6域庇。處理這個(gè)問題也很簡單嵌戈，首先對(duì)n÷5，移除所有的單個(gè)5听皿，然后÷25熟呛，移除額外的5，以此類推尉姨。
【參考答案】
