大数阶乘（下）

大数阶乘（下）

HDU 1042—题目要求计算10000！大约有35000~36000位，用上篇介绍的方法是满足不了需求的。分析，我们可以知道计算时所需要的时间耗费在进位处理上，由于我们使用10进制方式，结果导致计算长度len很大。为了减少计算时间，做一点改动，将进位改为10^10，这样进位长度大大缩减，由于10^10超过int的范围，我们使用__int64（注意，两个下划线）。提交到杭州电子科技大学的ACM判题系统显示耗时1720MS，如果想进一步减少时间可以通过扩大基数来实现，不过原理就类似了。

代码如下

#include

#include

using namespace std;

const int max_len=36000;//

const __int64 base5=100000;

const __int64 base=base5*base5;

__int64 x[max_len];

int len;

void fact(int n)

{

       __int64 carry;

       int i,j;

       for(i=0;i

              x[i]=0;

       x[0]=1;

       len=1;

       for(i=1;i<=n;++i)

       {

              carry=0;

              for(j=0;j

              {

                     x[j]=carry+x[j]*i;

                     carry=x[j]/base;

                     x[j]=x[j]%base;

              }

              while(carry)

              {

                     x[j++]=carry%base;

                     carry=carry/base;

                     len++;

              }

       }

}

int main()

{

       int n;

       while(scanf("%d",&n)!=EOF&&n>=0)

       {

              fact(n);

              int i;

              printf("%I64d",x[len-1]);

            for(i=len-2;i>=0;i--)

                                    {//Èôx[i]²»×ã9λÊý£¬Ç°Ãæ²¹Áã¡£

                                                if(x[i]<10)     printf("000000000");

                                                else if(x[i]<100)printf("00000000");

                                                else if(x[i]<1000)printf("0000000");

                                                else if(x[i]<10000)printf("000000");

                                                else if(x[i]<100000)printf("00000");

                                                else if(x[i]<1000000)printf("0000");

                                                else if(x[i]<10000000)printf("000");

                                                else if(x[i]<100000000)printf("00");

                                                else if(x[i]<1000000000)printf("0");

                                                printf("%I64d",x[i]);

                                    }

                                    printf("\n");

       }

       return 0;

}