ACM 大数阶乘 模板 原版+进阶+高级+最终（C++）+java版
目录
所有测试数据均为10000！
一.C++版
1.原版
思想：
用一个数组去存每一次阶乘的结果，仔细想想就能想出来。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<time.h>
#include<cstring>
using namespace std;
#define max 40000
int a[max];
void factorial(int n)
{
int i,j,add=0; //add为进位
a[0]=1;
for(i=1;i<=n;i++) // 思想是把阶乘结果存到一个数组里 ，每一次对数组进行处理
{
add=0;
for(j=0;j<max;j++)
{
a[j]=a[j]*i+add;
add=a[j]/10;
a[j]=a[j]%10;
}
}
for(i=max-1;i>=0;i--) //c从后往前，找到第一个不为0的数组单元
if(a[i])
break;
for(;i>=0;i--) //开始输出，每一个数组单元此时仅一位数字
printf("%d",a[i]);
}
int main()
{
clock_t start,end;
start=clock();
memset(a,0,sizeof(a));
int n;
cin>>n;
factorial(n);
end=clock();
cout<<endl<<"大数阶乘原版耗时："<<(float)(end-start)*1000.0/CLOCKS_PER_SEC<<"ms"<<endl;
return 0;
}结果：
2.进阶
for(j=0;j<max;j++)在i循环里还有一个j循环，这个j循环每次都是从0到max（max为40000），即便数组单元没有数值，他也照样循环，浪费时间，其实，j每次循环的次数为上一次结果的位数，就OK了，即i！的位数（从0开始，所以是i！，而不是（i-1）！），
咱也不知道咋让转90度，先这样看吧。
N!的位数=[lg(1)+lg(2)+…..lg(N)]+1([]表示向上取整) 向上取整，再+1，更保险
然后，就声明一个double数组存相应的位数。
具体见代码
#include<iostream>
#include<cmath>
#include<cstdio>
#include<time.h>
#include<cstring>
using namespace std;
#define max 40000
int a[max];
double b[max];
void factorial(int n)
{
int i,j,add=0;
a[0]=1;
b[0]=0;
for(i=1;i<max;i++) // 预处理每一位的位数
{
b[i]=b[i-1]+log10(i);
}
for(i=1;i<=n;i++)
{
add=0;
for(j=0;j<=(int)(b[i-1]+1);j++) //向上取整
{
a[j]=a[j]*i+add;
add=a[j]/10;
a[j]=a[j]%10;
}
}
for(i=(int)(b[n]+1);i>=0;i--) //h还有这个地方，也可以优化
if(a[i])
break;
for(;i>=0;i--)
printf("%d",a[i]);
}
int main()
{
clock_t start,end;
start=clock();
memset(a,0,sizeof(a));
int n;
cin>>n;
factorial(n);
end=clock();
cout<<endl<<"大数阶乘进阶版耗时："<<(float)(end-start)*1000.0/CLOCKS_PER_SEC<<"ms"<<endl;
return 0;
}
3.高级
我们知道：用来存放结果的数组是int型的，4个字节，能存21亿多，让一个数组单元存一位数，是不是有点太亏了，我们也不多存，就让他存5位数，那么原来存放每一次阶乘结果的位数的数组中的数值该怎么变？
每一单元从存放一位数到存放5位数，显然，存放结果位数的数组中的每一个数值变为原来的五分之一。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<time.h>
#include<cstring>
using namespace std;
#define max 40000
int a[max];
double b[max];
void factorial(int n)
{
int i,j,add=0;
a[0]=1;
b[0]=0;
for(i=1;i<max;i++)
{
b[i]=b[i-1]+log10(i);
}
for(i=1;i<=n;i++)
{
add=0;
int x=(int)(b[i]+1);
x=x/5;
for(j=0;j<=x;j++) //
{
a[j]=a[j]*i+add;
add=a[j]/100000;
a[j]=a[j]%100000;
}
}
for(i=(int)(b[n]+1)/5;i>=0;i--)
if(a[i])
break;
printf("%d",a[i--]);
for(;i>=0;i--)
printf("%05d",a[i]);
/*"%05d" 为什么会是他呢?
而不是"%d"？？？？？
因为如果结果为102000各位取余后res[0]=2000;
res[1]=1,输出的时候直接为12000,会出现错误，
这里你就明白了吧。*/
}
int main()
{
clock_t start,end;
start=clock();
memset(a,0,sizeof(a));
int n;
cin>>n;
factorial(n);
end=clock();
cout<<endl<<"大数阶乘进阶版耗时："<<(float)(end-start)*1000.0/CLOCKS_PER_SEC<<"ms"<<endl;
return 0;
}
4.最终
用一个b数组存放每一次结果的位数，是不是有点浪费空间了，能不能用a数组本身来达到b数组的效果？
当然能啦！
当每次j循环结束，对进位进行判断，是否大于0，则把进位填充到相应的位置。
不懂的话，看代码
#include<iostream>
#include<cmath>
#include<cstdio>
#include<time.h>
using namespace std;
#define LL int
void facterial(LL n)
{
int a[10000];
int i,j,l,c,m=0;
LL w;
a[0]=1;
for(i=1;i<=n;i++)
{
c=0;
for(j=0;j<=m;j++)
{
a[j]=a[j]*i+c;
c=a[j]/100000;
a[j]=a[j]%100000;
}
if(c>0) //如果有进位 用m*4存放上一次结果的位数
{
m++;
a[m]=c;
}
}
w=m*5+log10(a[m])+1; // 计算最终结果的位数
printf("%d",a[m]);
for(i=m-1;i>=0;i--)
{
printf("%05d",a[i]);
/*"%05d" 为什么会是他呢?
而不是"%d"？？？？？
因为如果结果为102000各位取余后res[0]=2000;
res[1]=1,输出的时候直接为12000,会出现错误，
这里你就明白了吧。*/
}
}
int main()
{
clock_t start,end;
start=clock();
LL n;
cin>>n;
facterial(n);
end=clock();
cout<<endl;
cout<<"最终版耗时："<<(float)(end-start)*1000.0/CLOCKS_PER_SEC<<"ms"<<endl;
return 0;
}
二.java版
用java解大数题简直开挂，记住java有BigDecimal类
package 大数;
import java.math.BigDecimal;
import java.util.Scanner;
public class 大数阶乘 {
public static BigDecimal factorial(BigDecimal n)
{
long start=System.currentTimeMillis();
BigDecimal a=new BigDecimal(1);
BigDecimal res=new BigDecimal(1);
while(n.compareTo(a)>0) //如果n>1
{
res=res.multiply(n); // res*n
n=n.subtract(a); // n=n-1;
}
return res;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
long start=System.currentTimeMillis();
Scanner in=new Scanner(System.in);
BigDecimal n=in.nextBigDecimal();
in.close();
System.out.println(n+"!=:"+factorial(n));
long end=System.currentTimeMillis();
System.out.println("当前程序运行了："+(end-start)+"ms");
}
}
切记：BigDecimal类的运算只能和同类进行操作。
开10000，不出结果，所以啊，还是自己老实的写吧，O(∩_∩)O哈哈~
如果你有不懂的地方，请留言，乐意解答。
最后，