转-超高精度算阶乘(快速) 雨中飞燕之家

超高精度算阶乘(快速)

 

//以10进制输出结果，本程序计算1000!用时不到50ms
#include <stdio.h>
#include <conio.h>
#include <time.h>  //用于计时
#define MaxNum        10000  //阶乘最大的数(最高位数)
//如果要算更大的n!请自行修改此值

void LargeNumberTimes(long *num,long &nMax,long nTimes)
{
    long z1,z2,z3=0;
    for(z1=0;z1<=nMax;z1++)
    {
        if((z2=num[z1]*nTimes+z3)>=10000)
        {
            z3=z2/10000,z2%=10000;
            if(z1==nMax)nMax++;
        }
        else z3=0;
        num[z1]=z2;
    }
}

int main()
{//雨中飞燕之作;
    long n,n1,nt,nMax=0,n0=0,n5=0,nc2=-10,nMod5,num[MaxNum]={1};
    scanf("%d",&n);//输入n，求n!
    long t=clock();//开始计时
    for(nMod5=n1=2;n1<=n;n1++,nMod5++)
    {
        if(nMod5==10)n0++,nc2++,nt=n1/10,nMod5=0;else
        if(nMod5==5)
        {
            n0++,nt=n1/5;
            while(nt%5==0 && nt)n0++,nt/=5;
        }
        else nt=n1;
        while(n0>=nc2 && (nt&1)==0 && nt)nc2++,(nt>>=1);
        if(nt>1)LargeNumberTimes(num,nMax,nt);
    }
    if((nc2+=10)>n0)LargeNumberTimes(num,nMax,(1<<(nc2-n0)));
    t=clock()-t;//结束计时
 
    printf("%d",num[nMax]);//输出计算结果
    for(n1=nMax-1;n1>=0;n1--)printf("%04d",num[n1]);
    for(n1=0;n1<n0;n1++)printf("0");printf("\n");
 
    printf("Time = %d ms",t);//输出用时
    getch();return 0;
}