ACM-大數之N！——hdu1042

N!

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 51640    Accepted Submission(s): 14540

Problem Description Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!

Input One N in one line, process to the end of file.

Output For each N, output N! in one line.

Sample Input

1
2
3
        

Sample Output

1
2
6
        

這道題題意很簡單，就是大數的乘法，N的階乘， 你也看到題目中 N可能到達10000， 是以，即使用Long long也是望塵莫及的。 這道題的方法就是： 建立一個整形數組，每個數組存五位數，大于五位的 num/100000進位，num%100000存起來 這道題的依據就是加法和乘法的配置設定率，用分段相乘： 1234*11=11*（12*10^2+34)=11*12*10^2+11*34， 上面是如果一個數組記憶體兩位，存五位也是類似的。

還要注意兩點： ①. 在乘的時候末尾可能出現很多0的情況，是以，什麼時候要向前算判定要清楚 ②. 在最後輸出的時候，除了最高位的不用補0，其他位數的都需要補0 第二個方法我用的是C的printf解決。

//N!


#include <stdio.h>
#include <string.h>
int arr[8001],k;

int main()
{
	int i,j,n,jinwei;
	int num;
	while(scanf("%d",&n)!=EOF)
	{
		memset(arr,0,sizeof(arr));
		arr[0]=1;

		
		k=0;
		// 從1到n循環
		for(j=1;j<=n;++j)
		{
			jinwei=0;
			for(i=0;i<=k;++i)
			{
				num=arr[i]*j+jinwei;
				if(num>99999)	jinwei=num/100000;
				else	jinwei=0;
				arr[i]=num%100000;
			
				// 如果到了最高位，仍有進位
				if(i==k && jinwei!=0)
				{
					++k;
					arr[k]=jinwei;
					break;
				}
			}
		}

		// 注意格式，第一個輸出的不需要補0，後面需要補0
		for(i=k;i>=0;--i)
			if(i==k)	printf("%d",arr[i]);
			else	printf("%05d",arr[i]);
		printf("\n");
	}
	return 0;
}