給定一個(gè)數(shù)N（N <= 10 ^ 1000），如何快速求得N！的最末位非零數(shù)是一個(gè)經(jīng)典的問(wèn)題。一直以來(lái)都被這個(gè)問(wèn)題困擾，今天仔細(xì)想了下，終于給想通了，盡管可能有些笨拙，現(xiàn)把想法記錄于此。
在N很小的情況下，有一個(gè)簡(jiǎn)便的方法：求出1到N之間每個(gè)數(shù)的2的因子數(shù)和5的因子數(shù)，記為F(2)和F(5)，顯然F(2) >= F(5)。由于在末尾只有2和5相乘才能產(chǎn)生0，如果我們把2和5拋去，那么肯定不會(huì)有0，這樣就可以一邊乘一邊模10，防止溢出。剩下的一堆2和5如何處理呢？因?yàn)?肯定比5多，因此最末位肯定是偶數(shù)（0的階乘和1的階乘除外）。而一個(gè)偶數(shù)不停地乘2，最末位的規(guī)律是：2 -> 4 -> 8 -> 6 -> 2 -> ...出現(xiàn)了4位1循環(huán)，這樣我們先用F(2) - F(5)，使得一部分2和5匹配上，2 * 5 = 10，對(duì)末尾不產(chǎn)生影響，剩下的2就模一下4，剩幾再乘幾次2就可以了。
但是這個(gè)方法在N非常大的時(shí)候肯定就不行了，但是可以利用找循環(huán)這個(gè)思想繼續(xù)做。如果算階乘的時(shí)候跳過(guò)5的倍數(shù)，記G(n)為跳過(guò)5的倍數(shù)的時(shí)候，從1乘到n的最末非零位，也就是把5的倍數(shù)當(dāng)1乘。可以發(fā)現(xiàn)：
G(1) = 1, G(2) = 2, G(3) = 6, G(4) = 4, G(5) = 4, G(6) = 4, G(7) = 8, G(8) = 4, G(9) = 6, G(10) = 6, G(11) = 6, G(12) = 2, G(13) = 6...
又出現(xiàn)了循環(huán)，每10個(gè)數(shù)循環(huán)一次。如何計(jì)算G(n)就變的很簡(jiǎn)單，求出n的最末位，就知道對(duì)應(yīng)的G(n)是多少了，當(dāng)然需要特判n = 1的情況。由于我們把5的倍數(shù)的數(shù)都提出來(lái)了，提出來(lái)的這些數(shù)（5、10、15、20、25、30...）每個(gè)除以5后又組成了一個(gè)階乘序列！除完5一共提出了n / 5個(gè)5，根據(jù)之前的分析，每個(gè)5都可以拿出一個(gè)2和它配對(duì)然后把它消去，這樣一個(gè)5就相當(dāng)于少一個(gè)2，我們就要把原來(lái)的數(shù)乘以3個(gè)2（模四循環(huán)）。這樣一來(lái)5的個(gè)數(shù)其實(shí)也可以模四，模完四之后剩k的話，就可以乘以k個(gè)8，就把所有的5消去了。現(xiàn)在總結(jié)一下：對(duì)一個(gè)數(shù)n的階乘，計(jì)算它的末尾非零位，先計(jì)算G(n)，相當(dāng)于非5的倍數(shù)的數(shù)的乘積最末非零位先算好了，然后乘以n / 5 % 4個(gè)8，處理了提出的n / 5個(gè)5，這樣之后還剩下n / 5的階乘沒(méi)有算。遞歸的求解n / 5的階乘的最末位非零數(shù)，再乘上去就得到結(jié)果了。
這個(gè)做法的復(fù)雜度就很低了，達(dá)到O(log n)，對(duì)于10 ^ 1000的數(shù)據(jù)，利用高精度做就行了。利用這種循環(huán)的思想，算排列數(shù)P(n, k)的最末非零數(shù)也就可以做到了。
附HOJ 1013代碼：
1
#include <cstdio>
2#include <cstring>
3const int N = 1024;
4
5
int hash[10] = 
{6, 6, 2, 6, 4, 4, 4, 8, 4, 6};
6int one_digit_hash[10] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8};
7
8int last_digit(char str[N], int st, int to)
9{
10
int i, tmp = 0, ret, num_of_five = 0;
11
12 if (st == to)
13 return one_digit_hash[str[st]-'0'];
14
15 ret = hash[str[to]-'0'];
16 for (i = st; i <= to; i++)
17
{
18 tmp = tmp * 10 + str[i] - '0';
19 str[i] = tmp / 5 + '0';
20 tmp %= 5;
21 num_of_five = (num_of_five * 10 + str[i] - '0') % 4;
22
}
23 if (str[st] == '0') st++;
24 ret = last_digit(str, st, to) * ret % 10;
25 while (num_of_five--) ret = ret * 8 % 10; //mul one 5 equals mul one 8
26
27 return ret;
28
}
29
30int main()
31{
32 char str[N];
33
34 while (scanf("%s", str) == 1)
35 printf("%d\n", last_digit(str, 0, strlen(str) - 1));
36
37 return 0;
38}
39