ACM-簡單題之Factorial——poj1401

轉載請注明出處：http://blog.csdn.net/lttree Factorial

Time Limit: 1500MS	Memory Limit: 65536K
Total Submissions: 13993	Accepted: 8678

Description

The most important part of a GSM network is so called Base Transceiver Station (BTS). These transceivers form the areas called cells (this term gave the name to the cellular phone) and every phone connects to the BTS with the strongest signal (in a little simplified view). Of course, BTSes need some attention and technicians need to check their function periodically. 

ACM technicians faced a very interesting problem recently. Given a set of BTSes to visit, they needed to find the shortest path to visit all of the given points and return back to the central company building. Programmers have spent several months studying this problem but with no results. They were unable to find the solution fast enough. After a long time, one of the programmers found this problem in a conference article. Unfortunately, he found that the problem is so called "Travelling Salesman Problem" and it is very hard to solve. If we have N BTSes to be visited, we can visit them in any order, giving us N! possibilities to examine. The function expressing that number is called factorial and can be computed as a product 1.2.3.4....N. The number is very high even for a relatively small N. 

The programmers understood they had no chance to solve the problem. But because they have already received the research grant from the government, they needed to continue with their studies and produce at least some results. So they started to study behaviour of the factorial function. 

For example, they defined the function Z. For any positive integer N, Z(N) is the number of zeros at the end of the decimal form of number N!. They noticed that this function never decreases. If we have two numbers N1 < N2, then Z(N1) <= Z(N2). It is because we can never "lose" any trailing zero by multiplying by any positive number. We can only get new and new zeros. The function Z is very interesting, so we need a computer program that can determine its value efficiently. 

Input

There is a single positive integer T on the first line of input. It stands for the number of numbers to follow. Then there is T lines, each containing exactly one positive integer number N, 1 <= N <= 1000000000.

Output

For every number N, output a single line containing the single non-negative integer Z(N).

Sample Input

6
3
60
100
1024
23456
8735373      

Sample Output

0
14
24
253
5861
2183837      

題目：http://poj.org/problem?id=1401

題目是求N！中末尾0的個數。

這道題，是我以前在經典例題100道中看到的，做出來的，但是，發現了解錯了。（感謝一位網友的提醒啊!）

是以，重新做一下，發現poj上有這道題，正好可以拿來測試一下做的是否正确。

這道題做法，顯然不能求出來階乘再數0的個數。

是以，要換一個思路。

為什麼會産生0呢？源于2x5,于是可以通過數有多少個（2,5）因子對來判斷有多少個0.

我們又可以發現，5的個數永遠會大于2的個數。

又可以簡化為數5的個數來做。

當時，還很年輕，做法讓現在的我看，有點糾結啊。。

當時做的是，從1到N（所輸入的數）循環，看看能不能被5整除，若能整除，繼續除5，直到不能整除為止。

這個做法顯然答案正确，但是在這道題裡，TLE必須的。。。

#include <stdio.h>
int main()
{
    int i,N,k,t;
    double num;
    bool prime;
    scanf("%d",&t);
    while( t-- )
    {
        scanf("%d",&N);
        k=0;
        for(i=1;i<=N;i++)           //檢視有多少個5
        {
            num=i/5.0;
            if(num-int(num)==0)
                prime=true;
            else
                prime=false;
            while(num>=1&&prime==true)
            {
                num/=5.0;
                if(num-int(num)==0)
                    prime=true;
                else
                    prime=false;
                k+=1;
            }
        }
        printf("%d\n",k);
    }
    return 0;
}
           

然後，現在想想，這道題，不需要這麼麻煩啊。

數5的倍數，就可以了。

以698為例：

698/5=139.6→取整→139     （表示有139個數為5的倍數） sum=sum+139 （sum初始化為0）

139/5=27.8 →取整→27        （表示有27個數為25的倍數）sum=sum+27    

（為什麼25的倍數，隻加了一遍，不應該加 27*2的嗎，25表示兩個5？      

因為，25的之前有一個5，在第一遍139個裡面算過一次了，是以不需要加兩遍。）

27/5=5.4 → 取整→5             （表示有5個數為125的倍數）sum=sum+5

5/5=1 → 取整 → 1      （表示有1個數為625的倍數） sum=sum+1

1/5=0  結束。

是以答案是   139+27+5+1=172

恩，是以程式，就很簡單了：

/************************************** 
*************************************** 
*        Author:Tree                  * 
*From :http://blog.csdn.net/lttree    * 
* Title : Factorial                   * 
*Source: poj 1401                     * 
* Hint  : N!求0的個數                * 
*************************************** 
**************************************/  
// scanf 125MS， cin 422MS
#include <stdio.h>
int main()
{
    // sum為答案，存儲每次除5後的數（累加）
    int t,n,sum;
    scanf("%d",&t);
    while( t-- )
    {
        sum=0;
        scanf("%d",&n);
        while( n )
        {
            n/=5;
            sum+=n;
        }
        printf("%d\n",sum);
    }
    return 0;
}