对于求大整数的阶乘,可以采用分段相乘的方法,其理论基础是加法的分配律,乘法的分配律。
for
exmaple
:123456789*123=123*(123*10^5+56789)=123*123*10^5+123*56789;
如果我们用一个数组result[0]=56789,result[1]=123,那么123456789*123就是123*result[0]%10^6和result[1]*123+result[0]/10^6构成的一个数,另result[0]=123*result[0]%10^6,result[1]=result[1]*123+result[0]/10^6,则这个数就是result[1]result[0];
#include
int
main()
{
int
n,j,i,t,p;
int
result[16000];
while(scanf("%d",&n)!=EOF){
t=p=0;result[0]=1;
//t记录result中所存数的个数
for(j=1;j<=n;j++){
//n!=1*2*3*4...*n;
for(i=0;i<=t;i++){
result[i]=result[i]*j+p;
//如果sum>99999不成立,则不需进位,进位为0
p=result[i]/100000;
//进位
result[i]%=100000;
//数组sum中每位存5位数字
}
if(p){
//t在最高位有进位的情况下++,最高位存进位
,并让进位为0
t++;
result[t]=p;
p=0;
}
//
如果进位不为0,
则下一次乘的时候将加上该进位,显然不合理
}
printf("%d",result[t]);//先把最高位输出,因为最高位没有前导0
for(i=t-1;i>=0;i--)
printf("%05d",result[i]);//s[i]不足5位,说明需补0
也说明result[i]在对100000取余的时候去掉了前导0,所以这里要加上
printf("\n");
}
return
0;
}