题目

题目链接：hdu 1066

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

思路

思路来源
稍微对上面的内容补充些自己的理解。

首先考虑N！，显然N！ = 1 * 2 * 3 * 4 * 5 * …… * N；在这里先做一个处理，每次遇到5的倍数就先乘2再除二，这也就是上面链接所说的将5当做1的原因。 这样处理的好处就是尾数在未除2时，会以10为周期方便计算。
所以当N>10时候，只需要10个分一组，由于6*6=6，所以只需最后乘上6即可。而N有[N/5]个5的倍数，就需要除于[N/5]个2，于是有递归式子：

$$F(N)=\frac{F[N/5]\ast table[N的尾数]\ast 6}{2^{[N/5]}}$$

而式子中的F(N/5)是什么意思呢？
由于我们前面将5的倍数乘于2，然后将其当做1处理，实际上是将他们提取出来，有如下一个表格：

5	10	15	20
10	20	30	40

忽略末尾的0，显然就有1 * 2 * 3 * 4，其结果就是F(N/5)。
而注意到2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 16, 2^5 = 32。以4为循环周期。
于是将分母的N/5 mod 4 即可。
更正式子为如下：

$$F(N)=\frac{F[N/5]\ast table[N的尾数]\ast 6}{2^{[N/5]Mod4}}$$

由于table以10为循环周期，2以4为循环周期，于是有
$$\frac{table[N的尾数]\ast 6}{2^{[N/5]Mod4}}$$以20为循环周期。

所以只需要打出上述的表格mod[20]={1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2}，去查找即可。由于本题的N较大，所以需要高精度计算。
至此解释完毕。

AC代码

#include <stdio.h>
#include <string.h>
#define Max 10000000

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[Max];
int a[Max];


int main() {
	int i, len, f, temp;
	while(~scanf("%s",&n)){
		f = 1;
		len = strlen(n);
		for(i = 0; i < len; i++){
			a[i] = n[len-1-i] - '0';
		}
		while(len){
			len -= !a[len-1];
			f = f * mod[a[1]%2*10 + a[0]] % 10;		//f为文中的F（N）
			for(temp = 0,i = len-1; i >= 0; i--){	//把数除于5
				temp = temp*10 + a[i];
				a[i] = temp/5;
				temp %= 5;
			}
		}
		printf("%d\n",f);
	}
}