hdu 1124 Factorial

題目位址：http://acm.hdu.edu.cn/showproblem.php?pid=1124

題目描述：

Factorial

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 1955    Accepted Submission(s): 1250

Problem 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
        

題意：求N的階乘出來的結果尾部有多少個連續的零。

題解：假設N！=   M x 10^n   即問題即是  給出N的值 求出n的值。這裡知道10=2 x  5的  而N！= 2^a  +  3^b +  5^c +  7^d +......  即所有的素數幂次和可以組成N！，那麼2^a+5^b=(2 x 5)^t;  即求t的值，由于2<5  那麼a〉b的  即 問題轉化為求N！中5這個素數因子的個數。而N！=1 x 2 x 3 x 4 x 5 x.....x N; 這裡每5個因子便會至少出現一次5

如1 x 2 x 3 x 4 x 5     6x7x8x9x10   11x12x13x14x15  16x17x18x19x20  21x22x23x24x25   這裡不難發現這樣的規律，那麼N/5  便是N！中第一遍出現的5，有第一遍那麼

就還有第二遍，如21x22x23x24x25中的25 實際上它是由兩個5的因子5x5,這樣可以總結為每5個因子的5個因子會出現第二個5，即1x2x3x4x5作為一個因子，這樣每隔5個

又會出現第二遍的5因子即5x5中的後面的那個5因子 以此類推125 就是第三遍了，這種5因子的不同遍數的出現時疊加的，其中第一遍的5因子貫穿所有乘數，而第二遍5

因子在25出現之後才開始連續出現  第三遍5因子在125出現之後才開始出現，由于具有這樣的疊代屬性（或者說是嵌套），那麼我們将N不斷地除以5  ，  然後再用除數除以5（這就是嵌套的5因子所在），除到不能除為止，然後把這些除數累加就是N！所有5因子的總數了，顯然第一次除以5留下來的除數就是第一遍5因子的個數了，以此類推。

相當于  N！中5因子的個數=N!/5+N!/25+N!/125+N!/5^4+.......N!/5^n=N不斷地用除以5得來的除數除以5；

代碼：

/*
hdu : Factorial

divide the quality factor and find the number of the 5 factor,nest interval 5

*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>

using namespace std;

int N=0,T=0,Cnt=0;

/*initialize the var*/
int InitVar()
{
    Cnt=0;
    return(0);
}

/*for test*/
int test()
{
    return(0);
}

/*main process*/
int MainProc()
{
    scanf("%d",&T);
    while(T--)
    {
        InitVar();
        scanf("%d",&N);
        while(N)
        {
            N/=5;
            Cnt+=N;
        }
        printf("%d\n",Cnt);
    }
    return(0);
}

int main()
{
    MainProc();
    return(0);
}