找規律！

求N！最後非0位的值。比如2是120的最後一個不是0的值。
輸入N比較大，要大數保存。
注意到最後0的個數是與5的因數的個數相等。設f（n）為n！的最後非0位。
那麼f(n)=((n%5)!* f(n/5) *2^(n/5))%10
因數2的個數始終大於5，從1開始每連續5個劃分為1組，其中5的倍數只提取出一個因數5後，
組成一個新的數列1到n/5，我們有1*2*3*4*5=6*7*8*9*5=2（取最後一個非0位），這裡就是2^（n/5）。
再乘上剩下來的幾個數字即可
（比如n是123，那麼第一次會剩下121,122,123三個數沒有被分配）。

例如：23 就可以變為 f(23) = ((3)! * f(4) * 2^(4))%10; f(4) = 4;

故f(23) = 4； 參考http://blog.csdn.net/yihuikang/article/details/7721875

 

Last non-zero Digit in N!

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


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

#include
#include
const int di[4] = { 6, 2, 4, 8};//這是2的次冪最後一位的循環；
const int pre[10] = { 1, 1, 2, 6, 4,2,2,4,2,8};//前十個數的最後一位； 
int a[200], ls;
char s[200];
void tran( int ls )//轉換 將個位放在a[0]處 
{
	for( int i =ls-1; i >= 0; i -- )
	a[ls-i-1] = s[i]-'0';
}
void mult(  )
{
	int i, t=0;//t是借位； 
	for( i = ls-1; i >= 0; i -- )
	{
		int q = t*10+a[i];
		a[i] = q/5;
		t = q%5;
	}
	while( ls > 0&&a[ls-1] == 0 ) --ls;//排除後面的0 仔細考慮一下
}
int la_no_num( )
{
	if( ls == 1 ) return pre[a[0]]; //如果只有一位直接輸出或返回
	int x1 = pre[a[0]%5];   //這是f（n%5）
	mult( );
	int x2 = di[(a[0]+a[1]*10)%4];//這是2^(n/5) 為什麼只算前兩位（提示：同余定理）
	int ans = (x1*x2*la_no_num())%10;//f(n)=((n%5)!* f(n/5) *2^(n/5))%10
	return ans;
}
int main()
{
	int la, i;
	while( ~scanf( "%s", s ) )
	{
		ls = strlen(s);
		tran(ls);	
		printf( "%d\n", la_no_num() );
	}
	
}