題意：

求n!的最后一位非零數(shù)。

題目：

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

分析：參考

我們發(fā)現(xiàn)n!末尾的0都是通過(guò)5和2想成得到的，為了把0去掉，我們把所有的因數(shù)2和5都提出來(lái)，放到最后再處理。

N!中的N個(gè)相乘的數(shù)可以分成兩堆：奇數(shù)和偶數(shù)。偶數(shù)相乘可以寫成$(2^M)?(M!)$，$M=N/2$。M!可以遞歸處理，因此現(xiàn)在只需討論奇數(shù)相乘。

考慮$1?3?5?7?9?11?13?15?17?...?N$(如果N為偶數(shù)則是N-1)，這里面是5的倍數(shù)的有5，15，25，35,…，可以其中的5提出來(lái),變成$(5^P)?(1?3?5?7?9?...)$，后面括號(hào)中共P項(xiàng)，$P=(N/5+1)/2$，而后面的括號(hào)又可以繼續(xù)提5出來(lái),遞歸處理.現(xiàn)在剩下的數(shù)是$1?3?7?9?11?13?17?19?....$這些數(shù)我們只需要他們的個(gè)位數(shù)，因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$(1?3?9?11?13?...)mod$ $10=(1?3?7?9?11?13?...)mod$ $10.$我們列出余數(shù)表，1 3 1 9 9 7 9 1 1 3 1 9 9 7 9 ……。我們發(fā)現(xiàn)每八項(xiàng)$mod$ 10的結(jié)果是一個(gè)循環(huán).

算出奇數(shù)的結(jié)果后，我們?cè)倩仡^看統(tǒng)計(jì)了多少個(gè)2和5需要乘入。把2和5配對(duì)完都是N!后面的0,看剩下的2有幾個(gè)。如果有剩下的2，考慮2^N的個(gè)位數(shù)又是2 4 8 6 2 4 8 6 ……每四項(xiàng)一個(gè)循環(huán)，找出這個(gè)個(gè)位數(shù)后，和前面的結(jié)果相乘，再取個(gè)位數(shù)就是答案。由于我們完全把2和5的因素另外處理，所以在所有的乘法中，都只需要計(jì)算個(gè)位數(shù)乘法，并且只保留個(gè)位數(shù)的結(jié)果。

由于是很大的數(shù)（前面三個(gè)點(diǎn)都可以不看Q—Q）
我們?cè)O(shè)F(N)表示N!的尾數(shù)。
先考慮簡(jiǎn)單的。考慮某一個(gè)N!(N < 10)，我們先將所有5的倍數(shù)提出來(lái)，用1代替原來(lái)5的倍數(shù)的位置。由于5的倍數(shù)全被提走了，所以這樣就不會(huì)出現(xiàn)尾數(shù)0了。我們先把$0?9$的階乘的尾數(shù)列出來(lái)（注意，5的倍數(shù)的位置上是1），可以得到table[0—9]=(1, 1, 2, 6, 4, 4, 4, 8, 4, 6)。對(duì)于N < 5，直接輸出table[N]即可；對(duì)于N>=5，由于提出了一個(gè)5，因此需要一個(gè)2與之配成10，即將尾數(shù)除以2。注意到除了0!和1!，階乘的最后一個(gè)非零數(shù)字必為偶數(shù)，所以有一個(gè)很特別的除法規(guī)律:$2/2=6,4/2=2,6/2=8,8/2=4$。比較特殊的就是$2/2=12/2=6,6/2=16/2=8$.這樣我們就可以得到如下式子：$F(N)=\{{}_{2^{N/5}}^{table[N]}(0<=N<10)$

• 再考慮復(fù)雜的。考慮某一個(gè)N!(N>=10)，我們先將所有5的倍數(shù)提出來(lái)，用1代替原來(lái)5的倍數(shù)的位置。由于5的倍數(shù)全被提走了，所以這樣就不會(huì)出現(xiàn)尾數(shù)0了。我們觀察一下剩下的數(shù)的乘積的尾數(shù)，通過(guò)table表，我們發(fā)現(xiàn)這10個(gè)數(shù)的乘積的尾數(shù)是6，6*6的尾數(shù)還是6，因此我們將剩下的數(shù)每10個(gè)分成一組，則剩下的數(shù)的乘積的尾數(shù)只與最后一組的情況有關(guān)，即與N的最后一位數(shù)字有關(guān)。(因?yàn)楦鶕?jù)最后一位就能知道它在尾數(shù)表中處于第幾個(gè)位置，只要將尾數(shù)表之前的數(shù)相乘就得到最后一組的尾數(shù)。）由于我們把5的倍數(shù)提出來(lái)了，N!中一次可以提出[N/5]個(gè)5的倍數(shù)，有多少個(gè)5，就需要有多少個(gè)2與之配成10，所以有多少個(gè)5，最后就要除以多少個(gè)2。注意到除2的結(jié)果變化是4個(gè)一循環(huán)，因此如果有A個(gè)5，只需要除(A MOD 4)次2就可以了。A MOD 4只與A的最后兩位數(shù)有關(guān)，很好求算。剩下的5的倍數(shù)，由于5已經(jīng)全部處理掉了，就變成[N/5]!。于是，我們可以得到
  一個(gè)遞歸關(guān)系：
  $F(N)=\{{}_{2^{[N/5]mod4}}^{F[N]?table[N的尾數(shù)]?6}(N>10)$
  這樣我們就得到了一個(gè)O(log5(N))的算法，整除5可以用高精度加法做，乘2再除10即可。整個(gè)算法相當(dāng)巧妙。

AC代碼：

#include<stdio.h> #include<string.h> #include<iostream> using namespace std; const int M=1e3+10; const int mp[20]= {1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2}; char s[M]; int main() {while(~scanf("%s",s)){int n=strlen(s),ret=1,a[M];if(n==1)printf("%d\n",mp[s[0]-'0']);else{for(int i=0; i<n; i++)a[i]=s[n-1-i]-'0';while(n>1){if(a[n-1]==0)n--;ret=ret*mp[a[1]%2*10+a[0]]%5;int num=0;for(int i=n-1; i>=0; i--)//num=num/5{num=num*10+a[i];a[i]=num/5;num%=5;}}printf("%d\n",ret+ret%2*5);}}return 0; }

如何求n！中5的個(gè)數(shù)

int get5(int n)//計(jì)算n!中質(zhì)因子5的出現(xiàn)次數(shù) {if(n==0)return 0;return n/5+get5(n/5); }

總結(jié)

以上是生活随笔為你收集整理的Last non-zero Digit in N! HDU - 1066的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。