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从1开始求阶乘,如果结果大于10000则将大于的部分在前一个res数组元素中保存,以此类推用
res计算阶乘结果。输出的时候最左边的四个数单独输出,后面的每个4位数如果前几位为0则需要在前面补零补齐4位输出。
AC代码:
#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
int res[10010];
int n;
void Solve() {
int Book = 1;
int BaoFour = 0;
res[Book] = 1;
for (int i = 1;i <= n;++i) {
BaoFour = 0;
for (int j = 1;j <= Book;++j) {
res[j] = res[j] * i + BaoFour;
BaoFour = res[j] / 10000;
res[j] = res[j] % 10000;
}
if (BaoFour > 0) {
res[++Book] += BaoFour;
}
}
cout << res[Book];
for (int i = Book - 1;i > 0;--i) {
if (res[i] >= 1000) {
cout << res[i];
}
else if (res[i] >= 100) {
printf("0%d",res[i]);
}
else if (res[i] >= 10) {
printf("00%d",res[i]);
}
else {
printf("000%d",res[i]);
}
}
cout << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
while (cin >> n) {
mem(res, 0);
Solve();
}
return 0;
}