LFYZ-OJ ID: 1009 阶乘和

时间:2023-03-09 16:53:58
LFYZ-OJ ID: 1009 阶乘和

思路

  • 循环n次,每次计算i的阶乘i!,并加入sum中。

  • n的范围从1~100,这里一定要使用高精度运算,涉及到“高精度乘低精度”,“高精度加高精度”。

  • 避免每次重复计算i!(i+1)!等于上一轮计算的i!*(i+1),因此在循环的n次过程中,每次做一次乘法(计算i!)、一次加法(将i!累加到sum中),即可得到结果。

  • 使用两个数组空间存储高精度数字,njc[300]用于计算i的阶乘、sum[300]用于累加和。

例程

#include<iostream>
using namespace std;
int njc[300]; //n!,全局数组,默认初始化为0
int sum[300]; //累加和,全局数组,默认初始化为0
void print(int num[]){ //结果打印函数
for(int i=num[0]; i>=1; i--) printf("%d", num[i]);
}
int main(){
int n;
scanf("%d", &n);
njc[0]=1, njc[1]=1; //初始化ncj=1!,0单元存储长度
sum[0]=1, sum[1]=1; //初始化sum=1!,0单元存储长度
for(int i=2; i<=n; i++){ //i从2循环至n
int jw=0;
for(int j=1; j<=njc[0]; j++){ //njc*i,得到 i!
njc[j]=njc[j]*i+jw;
jw=njc[j]/10;
njc[j]%=10;
}
if(jw){ //乘数最多为2位数,位数最多增加2
if(jw>=10) { njc[njc[0]+1]=jw%10; njc[njc[0]+2]=jw/10; njc[0]+=2; }
else { njc[njc[0]+1]=jw; njc[0]+=1;}
} int max_ws=max(sum[0], njc[0]); //max(njc, sum)
jw=0;
for(int j=1; j<=max_ws; j++){
sum[j]=sum[j]+njc[j]+jw;
jw=sum[j]/10;
sum[j]%=10;
} //确定位数
if(jw) { sum[max_ws+1]=jw; sum[0]=max_ws+1; }
else sum[0]=max_ws;
}
print(sum); //输出结果
return 0;
}