P1009 [NOIP1998 普及組] 階乘之和（c++）

階乘之和其實就是每個高精度的乘積加上高精度的加法。如果對裡面的代碼有些疑惑可以去看我的另外一篇部落格。

高精度的計算詳解

完整代碼：

#include<iostream>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<vector>
using namespace std;
const int Maxn=10000;
ostream&operator<<(ostream &o,int result[]){
    o<<result[result[0]];
    for(int i=result[0]-1;i>0;i--){
        o.width(4);//每次都要輸出4位
        o.fill('0');//如果不夠4位則要補齊，因為int類型裡面的0000會被當作0
        o<<result[i];
    }
    return o;
}
void addition(int num1[],int num2[]){//加法
    int result[Maxn];
    memset(result,0,sizeof(result));
    result[0]=max(num1[0],num2[0]);
    for(int i=1;i<=result[0];i++){
        result[i]+=num1[i]+num2[i];
        if(result[i]>=10000){//則要進行進位
            result[i]-=10000;
            result[i+1]++;//往前進位
        }
    }
    //下面是關鍵
    if(result[result[0]+1]>0){//類似于9999+1，則會多一位出來，就要判斷是否多了一位。
        result[0]++;
    }
    for(int i=0;i<=result[0];i++){//将答案傳到num數組中，傳出去
        num1[i]=result[i];
    }
}
void multiplication(int num1[],int num2[]){//乘法
    int result[Maxn];
    memset(result,0,sizeof(result));
    result[0]=num1[0]+num2[0]+1;
    for(int i=1;i<=num1[0];i++){
        for(int j=1;j<=num2[0];j++){//就是豎式算法一樣，一步步來求
            result[i+j-1]+=num1[i]*num2[j];//減1是為了從第一位開始
            result[i+j]+=result[i+j-1]/10000;//進位
            result[i+j-1]%=10000;
        }
    }
    //下面是關鍵
    while(result[result[0]]==0&&result[0]>0){//就是把前面多餘的0删除
        result[0]--;
    }
    for(int i=0;i<=result[0];i++){//将答案傳到num數組中，傳出去
        num1[i]=result[i];
    }
}
void factorial_content(int n,int result[]){//一個階乘
    int num1[Maxn];
    int num2[Maxn];
    memset(num1,0,sizeof(num1));
    memset(num1,0,sizeof(num1));
    num1[0]=1;
    num1[1]=n;
    num2[0]=1;
    for(int i=n-1;i>=2;i--){
        num2[1]=i;
        multiplication(num1,num2);
    }
    for(int i=0;i<=num1[0];i++){
        result[i]=num1[i];
    }
}
void factorial(int n){//各個階乘的和
    int result[Maxn];
    int finally[Maxn];
    memset(finally,0,sizeof(finally));
    for(int i=n;i>=2;i--){
        memset(result,0,sizeof(result));
        factorial_content(i,result);
        addition(finally,result);
    }
    memset(result,0,sizeof(result));
    result[0]=1;
    result[1]=1;
    addition(finally,result);
    cout<<finally;
}
int main(){
    int n;
    cin>>n;
    factorial(n);
    system("pause");
    return 0;
}