[重返NOIP] 高精度——NOIP1998 普及组 阶乘之和

题目描述

用高精度计算出 S = 1! + 2! + 3! + … + n! （ n <= 50 ）。

其中 ! 表示阶乘，定义为 n!=n (n-1) (n-2) … 1 。例如， 5! = 5 4 3 2 1=120 。

输入格式

一个正整数 n 。

输出格式

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

样例 #1

样例输入 #1

3
copy

样例输出 #1

9
copy

提示

【数据范围】

对于 100 % 的数据， 1 <= n <= 50 。

思路

看了一下大部分题解，其实也没有别的考察点，主要就是高精加套高精乘，方法也有很多，下面主要介绍两种该思路的实现方法

方法一

这种方法主要使用结构体去封装大整数，让大整数能像普通整型一样直接相加相乘，下面是封装的结构体

#define MAXN 50000
struct bigint{
    int len,a[MAXN];//len记录位数，a记录每个数位
    bigint(int x=0){//通过初始化使得这个大整数能够表示整型x，默认为0
        memset(a,0,sizeof(a));
        for(len=1;x;len++){
            a[len]=x%10,x/=10;
        }
        len--;
    }
    int  &operator[](int i){
        return a[i];  //重载[]，可以直接用x[i]代表x.a[i]
    }
    void flatten(int L){//一口气处理1到L范围内的进位并重置长度。需要保证L不小于有效长度
        //简单说就是将数组每个位置经过进位后都变成一位数
        len=L;
        for(int i=1;i<=len;i++){
            a[i+1]+=a[i]/10;
            a[i]%=10;
        }
        for(;!a[len];){//重置长度为有效长度
            len--;
        }
    }
    void print(){
        for(int i=max(len,1);i>=1;i--){
            printf("%d",a[i]);
        }
    }
    bigint operator+(bigint a,bigint b){//表示两个bigint类相加，返回一个bigint类
         bigint c;
         int len=max(a.len,b.len);
         for(int i=1;i<=len;i++){
             c[i]+=a[i]+b[i];
         }
         c.flatten(len+1);//答案不可能超过len+1位，所以用len+1做进位处理
         return c;
    }
    bigint operator*(bigint a,bigint b){
        bigint c;
        int len=a.len;
        for(int i=1;i<=len;i++){
            c[i]=a[i]*b;
        }
        c.flatten(len+1);//int类型最长10位，所以可以这样做一遍进位处理
    }
};
copy

封装完后，就需要主函数对接接口直接使用了

int main(){
    bigint ans(0),fac(1);//分别用0，1初始化ans和fac，如果要将常数赋值给大整数，可以使用类似于ans=bigint(233)的办法
    int m;
    cin>>m;
    while(m--){
        fac*=i;
        ans+=fac;
    } ans.print();
}
copy

代码来源——《深入浅出——程序设计竞赛（基础篇）》

有没有发现什么问题？如果你拿上面的代码去提交的话，大概率是不会通过原题OJ的。原因出在哪呢？
关键就在于当阶乘数不断变大，构造函数的输入接口x就无法承载下更大数字。经过官方测试的结果，上面代码只能承载n<=20的结果。
如果还是要用上面的方法，那么接口也需要进行高精度处理。我个人的解决方案有两种：
一是将接口类型也修改为bigint，然后将原构造函数的内容转移到另一个功能函数进行位数处理，新的构造函数采用流输入来将接受大整数并直接读入数组。但实现起来比较麻烦。
另一种则是将大整数当成字符串读入，修改原接口类型为string或char数组，逐一放进结构体中处理成数字即可

方法二

我个人更喜欢自己的方法，同样拥有上述结构体中的功能，而且实现起来也更加便捷

#include<stdio.h>
int main()
{
    int i,A[1005]={0},B[1005]={0},n,j;
    scanf("%d", &n);
    A[0]=B[0]=1;
    for (i=2;i<=n;i++){
        for (j=0;j<100;j++)
            B[j]*=i;
        for (j=0;j<100;j++)
            if (B[j]>9){
                B[j+1] += B[j]/10;
                B[j]%=10;
            }
        for (j=0;j<100;j++){
            A[j]+=B[j];
            if (A[j]>9) {
                A[j+1] += A[j]/10;
                A[j]%=10;
            }
        }
    }
    for (i=100;i>=0&&A[i]==0;i--);
    for (j=i;j>=0;j--) printf("%d", A[j]);
    return 0;
}
copy