Last non-zero Digit in N!

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6432 Accepted Submission(s): 1593


Problem Description The expression N!, read as "N factorial," denotes the product of the first N positive integers, where N is nonnegative. So, for example,
N N!
0 1
1 1
2 2
3 6
4 24
5 120
10 3628800

For this problem, you are to write a program that can compute the last non-zero digit of the factorial for N. For example, if your program is asked to compute the last nonzero digit of 5!, your program should produce "2" because 5! = 120, and 2 is the last nonzero digit of 120.

Input Input to the program is a series of nonnegative integers, each on its own line with no other letters, digits or spaces. For each integer N, you should read the value and compute the last nonzero digit of N!.

Output For each integer input, the program should print exactly one line of output containing the single last non-zero digit of N!.

Sample Input

1 
2 
26 
125 
3125 
9999

Sample Output

1
2
4
8
2
8

Source South Central USA 1997

題意：求N！的最後一個非0數字。

解析：

這道題要求N!的最後一個非0數字是多少，如果用一般作法，先統計2和5的個數，然
後補乘2，得到的將是TLE。所以還需要再做簡化：

為了把0去掉，我們把所有的因數2和5都提出來，放到最後再處理。N!中的N個相乘的
數可以分成兩堆：奇數和偶數。偶數相乘可以寫成(2^M)*(M!)，M=N DIV 2。M!可以
遞歸處理，因此現在只需討論奇數相乘。考慮1*3*5*7*9*11*13*15*17* ... *N(如果
N為偶數則是N-1)，這裡面是5的倍數的有5，15，25，35，... ，可以其中的5提出來
，變成(5^P)*(1*3*5*7*9* ... )，後面括號中共P項，P=(N DIV 5+1) DIV 2，而後
面的括號又可以繼續提5出來，遞歸處理。現在剩下的數是1 * 3 * 7 * 9 * 11 * 13
* 17 * 19 * ... 。這些數我們只需要他們的個位數，因為(1 * 3 * 9 * 11 * 13
* ... ) MOD 10 = (1 * 3 * 7 * 9 * 1 * 3 * ... ) MOD 10。我們列出余數表，
1 3 1 9 9 7 9 1 1 3 1 9 9 7 9 ……。我們發現每八項MOD 10的結果是一個循環。
算出奇數的結果後，我們再回頭看統計了多少個2和5需要乘入。把2和5配對完都是N
!後面的0，看剩下的2有幾個。如果有剩下的2，考慮2^N的個位數又是2 4 8 6 2 4
8 6 ……每四項一個循環，找出這個個位數後，和前面的結果相乘，再取個位數就是
答案。由於我們完全把2和5的因素另外處理，所以在所有的乘法中，都只需要計算個位數乘法，並且只保留個位數的結果。

但讓我很驚異的是：為什麼我提交總是WA？後來我才知道，原因是這道題的N相當大
！達到了10^100！要用大數來處理！GPC四項編譯開關全關的，自然查不出來！而且
上面這個算法換成大數後會很麻煩。還有什麼別的好方法嗎?

答案是有的。我們設F(N)表示N!的尾數。

先考慮簡單的。考慮某一個N!(N < 10)，我們先將所有5的倍數提出來，用1代替原來
5的倍數的位置。由於5的倍數全被提走了，所以這樣就不會出現尾數0了。我們先把
0..9的階乘的尾數列出來（注意，5的倍數的位置上是1），可以得到table[0..9] =
(1, 1, 2, 6, 4, 4, 4, 8, 4, 6)。對於N < 5，直接輸出table[N]即可；對於N >
= 5，由於提出了一個5，因此需要一個2與之配成10，即將尾數除以2。注意到除了0
!和1!，階乘的最後一個非零數字必為偶數，所以有一個很特別的除法規律：2 / 2
= 6，4 / 2 = 2，6 / 2 = 8，8 / 2 =　4。比較特殊的就是2 / 2 = 12 / 2 = 6，
6 / 2 = 16 / 2 = 8。這樣我們就可以得到如下式子：
代碼:

table[N]
F(N) = ------------ (0 <= N < 10)
2^([N/5])

再考慮復雜的。考慮某一個N!(N >= 10)，我們先將所有5的倍數提出來，用1代替原
來5的倍數的位置。由於5的倍數全被提走了，所以這樣就不會出現尾數0了。我們觀
察一下剩下的數的乘積的尾數，通過table表，我們發現這10個數的乘積的尾數是6，
6 * 6的尾數還是6，因此我們將剩下的數每10個分成一組，則剩下的數的乘積的尾數
只與最後一組的情況有關，即與N的最後一位數字有關。由於我們把5的倍數提出來了
，N!中一次可以提出[N/5]個5的倍數，有多少個5，就需要有多少個2與之配成10，所
以有多少個5，最後就要除以多少個2。注意到除2的結果變化是4個一循環，因此如果
有A個5，只需要除(A MOD 4)次2就可以了。A MOD 4只與A的最後兩位數有關，很好求
算。剩下的5的倍數，由於5已經全部處理掉了，就變成[N/5]!。於是，我們可以得到
一個遞歸關系：
代碼:

F([N/5]) * table[N的尾數] * 6
F(N) = ----------------------------------- (N > 10)
2^([N/5] MOD 4)

這樣我們就得到了一個O(log5(N))的算法，整除5可以用高精度加法做，乘2再除10即
可。整個算法相當巧妙，寫起來也比較輕松。

因為 2^N 是以4為循環節的
而且table[N]是以10為循環節的
所以從10開始
F([N/5]) * table[N的尾數] * 6
F(N) = ----------------------------------- (N > 10)
2^([N/5] MOD 4)
右邊的式子除了F[n/5]外 是以20為循環節的
寫出循環的末尾數字mod[20]={1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2}

整體思路就是這樣了。

注：以上解析借鑒自：無名的博客

AC代碼：

#include
#include
int mod[20]={1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2};
char n[1000];
int a[1000];
int main()
{
 int i,c,t,len;
    while(scanf("%s",n)!=EOF)
 {
  t=1;
  len=strlen(n); 
  for(i=0;i=0;i--)      
    c=c*10+a[i],a[i]=c/5,c%=5;
  }
  printf("%d\n",t);
 }
 return 0;
}