HDU 1042 N!（高精度階乘、大數乘法）

N!

Time Limit: 10000/5000 MS (Java/Others)????Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 100274????Accepted Submission(s): 30006

?

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是小于10000的，所以每次都是乘一個int可以存下的數，但是另一個乘數可能是一個大數，所以稱之為大數乘小數。

那么如何計算呢：

用字符數組存大數，然后和大數加法很像，與豎式計算一樣的原理，大數的每一位都要去乘這個小數，模10是當前位上的值，除以10是進位。

與大數加法略有不同的是，大數要倒著存，比如123 就要anss[1]=3，anss[2]=2,anss[3]=1，這是因為加法的進位只會進一位，乘法進位可能會進好幾位，倒著存容易處理。

代碼

#include<bits/stdc++.h>using namespace std;
int anss[1000000],n,cnt,i,j,k,temp;
int main()
{while(scanf("%d",&n)!=EOF){memset(anss,0,sizeof(anss)); anss[1]=1;cnt=1;                            //記錄當前結果長度 for(i=1;i<=n;i++){k=0;                        //記錄進位 for(j=1;j<=cnt;j++){temp=(anss[j]*i+k)%10;k=(anss[j]*i+k)/10;anss[j]=temp;} while(k){anss[++cnt]=k%10;k=k/10;}}for(i=cnt;i>=1;i--)printf("%d",anss[i]);printf("\n");}
}

?

?

?