阶乘之和 (洛谷 P1009题)

首先,题目传送门是一定要有的 接下来就是题目描述了

题目描述

用高精度计算出S=1!+2!+3!+…+n! (n≤50) 其中“!”表示阶乘，例如：5!=5×4×3×2×1。

输入格式

一个正整数N。

输出格式

一个正整数S，表示计算结果。

输入输出样例

输入 #1

3

输出 #1

9

说明/提示

注:《深入浅出基础篇》中使用本题作为例题，但是其数据范围只有 n<=20，使用书中的代码无法通过本题。 如果希望通过本题，请继续学习第八章高精度的知识。

好了,题目看完了,首先肯定要定义变量对吧,因为考虑到1!+2!+3!+…+50!可能会很大,所以定义的变量要尽可能地大,因为题目限制内存在125MB之内,所以int类型的数组最大的长度为125MB/4B=32768000考虑到后面还会有变量,故把数组长度设置为3276800接下来就是高精度阶乘和高精度加法,如果你学习过高精度,接下来的部分你可以掠过,没有学习过的可以看一下加粗部分的字

首先是高精度加法,其实就是循环把每一位都加起来,比如42954+69837,计算过程如下: 4+7=11,11>=10,所以进位就是1,这一位就变成了1; 3+5+1=9,9<10,所以进位就是0,这一位就还是9; 8+9=17,17>=10,所以进位就是1,这一位就变成了7; 2+9+1=12,12>=10,所以进位就是1,这一位就变成了2; 4+6+1=11,11>=10,所以进位就是1,这一位就变成了1; 所以最后的结果为112791 乘法也一样,只不过多了些进位而已,知道了这些,就可以做高精度阶乘了. 接下来,上代码!

源代码

#include <cstdio> #include <iostream> #include <cstring> #include <climits> using namespace std; int fac[16328],sum[16328]={0};//fac代表每次的阶乘数,sum代表最后加和 int nmax=INT_MIN;//随后输出数量取fac的最大长度,所以需要nmax int factorial(int n){//定义求阶乘函数 fac[1]=1;//首先将fac设为1 int mul=1,len=1;//mul为每次的乘数,len为fac的长度 while(n--){ int carry=0;//carry为进位 for(int i=1;i<=len;i++){ fac[i]=fac[i]*mul+carry;//下一个数等于上一个数乘以乘数加进位 carry=fac[i]/10;//进位等于求出的数的除个位以外的数 fac[i]=fac[i]%10;//而留下的数则是各位 } mul++;//每次乘数变大1 while(carry){ fac[++len]=carry%10;//在len长度以外的数用这种方法处理 carry/=10;//随后只留下carry的个位 } } return len;//以后要用,需要返回 } int main(){ int n,tmptmp=0; cin>>n;//输入n; for(int i=1;i<=n;i++){ int tmp=factorial(i);//得到len并赋给tmp if(tmp>nmax) nmax=tmp;//打擂台求最大 for(int j=1;j<=tmp;j++){ sum[j]+=fac[j]; sum[j]+=tmptmp;//tmptmp为进位 if(sum[j]>=10){ tmptmp=1;//如果>=10则进一位 sum[j]-=10;//然后求出这一位的真正数值 }else tmptmp=0;//否则进位归零 } } for(int i=nmax;i>=1;i--) cout<<sum[i];//反向输出 return 0; }