高精度阶乘的实现(hdu acm 1042 N!)

求N!，由 N！＝N*（N－1）！，所以求解N！的算法就是递推法。
当N值很小时可以直接用int型数据进行运算就可以解决了，但当N值很大，比如N＝10000或跟大时就没有办法用具体的数据类型来存放这样大的，因为他们的为数都远远超过了int ，long甚至long long型的范围（如10000！有35660位）。
为了解决所有数据类型都无法存放这样一个庞大的数据，我向到了可以将这样一个数据一位一位的存放到一个字符数组或int型数组中，对其每一位进行单独运算，然后将结果存放到另一个数组里，这样就解决了庞大数据的存放问题。但具体怎样对两个都比较大的数的作乘法运算呢？这就要利用大整数的高精度运算。A,B都是位数比较多的大整数，现在要作A*B运算。小学时我们作45*12是先把12中的2与45的个位5相乘，再把2与45的十位4相乘，然后同样再把12中的1与45中的每一位从低到高依次相乘。在这里我们模拟也可以45*12，把A中每一位从低到高与B中的个位相乘，与后再与B中的十位相乘，依次类推，最后把所有的结果对应相加就可以得到所要求的结果了。
我们用a[100000]来存N!的结果,如十进制数3478,存在a里面是:a[0]=4(记录数的长度),a[1]=8,a[2]=7,

a[3]=4,a[4]=3;

//实现代码如下:

#include
using namespace std;
int a[40000];
int main()
{
 int N,i,j,pre;
 
 while(cin>>N)
 {
  a[0]=1;a[1]=1;
  if(N==0||N==1)
  {
   cout<<1<   continue;
  }
  for(i=2;i<=N;i++)
  {
   pre=0;
   for(j=1;j<=a[0];j++)
   {
    a[j]*=i;
    a[j]+=pre;//加上进位
    pre=a[j]/10;//进位值
    a[j]%=10;//本位
   }
   while(pre)//对末尾的进位进行存储
   {
    a[j]=pre%10;
    a[0]=j;
    pre/=10;
    j++;
   }
  }
  for(i=a[0];i>=1;i--)//输出
   cout<  cout< }
 return 0;
}

//hdu 1042 通过,耗时1850MS

//但是上面算法的效率不高,10000!的阶乘要将近2S才能算出来,不能解决实际问题.为了达到更好的效果,必须进行优化.在杭电的论坛上看到有人用类似的方法,但进行了改进,原理是大小不同的数的加法运算时间是基本相等的(<算法艺术与信息学竞赛> 黄亮,刘汝佳著).上面的程序是由于每一位每一位相加求得,但数非常大时,位数会很多,每进行一次乘都要进行几万位的运行,累计起来,这是一个非常大的时间开销.我们何不在数位的每个元素中存放在5-10位,而不是1位.(int型最多5位,因为两个5位数相乘不会超出整型范围,6位就超了,也可采用能表达的更大的数据类型,那样时间更省.)

//代码如下:

#include
using namespace std;
#define M 10000000000
unsigned __int64 a[20000];
int main()
{
 int N,i,j;
 unsigned __int64 pre;
 while(cin>>N)
 {
  a[0]=1;a[1]=1;
  if(N==0||N==1)
  {
   cout<<1<   continue;
  }
  for(i=2;i<=N;i++)
  {
   pre=0;
   for(j=1;j<=a[0];j++)
   {
    a[j]*=i;
    a[j]+=pre;
    pre=a[j]/M;
    a[j]%=M;
   }
   while(pre)
   {
    a[j]=pre%M;
    a[0]=j;
    pre/=M;
    j++;
   }
  }
  printf("%I64u",a[a[0]]);
  for(i=a[0]-1;i>0;i--)
  {
   if(a[i]<10) cout<<"000000000";
   else if(a[i]<100) cout<<"00000000";
   else if(a[i]<1000) cout<<"0000000";
   else if(a[i]<10000) cout<<"000000";
   else if(a[i]<100000) cout<<"00000";
   else if(a[i]<1000000) cout<<"0000";
   else if(a[i]<10000000) cout<<"000";
   else if(a[i]<100000000) cout<<"00";
   else if(a[i]<1000000000) cout<<"0";
   printf("%I64u",a[i]);
  }
  cout< }
 return 0;
}

//hdu 1042用C++提交通过 耗时1430MS,比开始那个节省了几百MS..(用G++提交不能通过,因为G++不支持64位整).

如果哪位高手有更好的方式请多多交流...