nyoj 题目28 大数阶乘

http://acm.nyist.net/JudgeOnline/problem.php?pid=28

大数阶乘

描述

我们都知道如何计算一个数的阶乘，可是，如果这个数很大呢，我们该如何去计算它并输出它？

输入

输入一个整数m(0<m<=5000)

输出

输出m的阶乘，并在输出结束之后输入一个换行符

样例输入

50

样例输出

30414093201713378043612608166064768844377641568960512000000000000

#include<stdio.h>
#include<string.h>
#define MAX 10000
//这里如果MAX给20000运行时间是2776ms，如果MAX给10000，运行时间是1816ms
//还得优化算法
int main()
{
    int N,i,j,k,n,m,a[2*MAX],J[2*MAX],b[10];
    char s[10];
    while(scanf("%d",&N)!=EOF)
    {
        memset(a,sizeof(a));
        a[0]=1;//开始就是1的阶乘

        for(i=2;i<=N;i++)
        {
//             memset(b,sizeof(b));
//             for(j=0,k=10;j<10;j++,k*=10)
//             b[j]=i%k/(k/10);//将i逆序存放到b[]数组中

             memset(s,'',sizeof(s));
             sprintf(s,"%d",i);
             m=strlen(s);//这里要知道m，下边要用m,如果在下边算大数乘法时直接循环10，会超时；
             //这里是为了缩短时间,还得优化算法，那样就不用考虑这么多了
             for(k=0,j=m-1;j>=0;j--,k++)
             b[k]=s[j]-'0';

             for(j=2*MAX-1;j>0;j--)//这里知道a的位数也是为了缩短时间
             if(a[j]!=0) break;
             n=j;

             memset(J,sizeof(J));
             for(j=0;j<m;j++)
                for(k=0;k<=n;k++)
                J[j+k]+=a[k]*b[j];
             for(j=0;j<2*MAX;j++)
             {
                 if(J[j]>=10)
                 {
                     J[j+1]+=J[j]/10;
                     J[j]=J[j]%10;
                 }
             }

             memset(a,sizeof(a));
             for(j=0;j<2*MAX;j++)
             a[j]=J[j];
        }

        for(i=2*MAX-1;i>0;i--)
        if(a[i]!=0) break;
        for(;i>=0;i--)
        printf("%d",a[i]);
        printf("n");
    }
    return 0;
}