[NOIP] - 阶乘之和

image

题目描述

用高精度计算出S=1!+2!+3!+…+n! (n≤50)S=1!+2!+3!+…+n!(n≤50)

其中“!”表示阶乘，例如：5!=5 \times 4 \times 3 \times 2 \times 15!=5×4×3×2×1。

输入输出格式

输入格式：

一个正整数NN。

输出格式：

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

分析

当n = 50时，结果为：

31035053229546199656252032972759319953190362094566672920420940313

没有一个适当的类型可以容纳这么长的一串数字，按正常的思路做，会导致溢出的异常，可以考虑将结果垵位保存到数组中，然后垵位输出。

思路：见图

image

代码

---

#include <iostream>
#include <string.h>


using namespace std;

int ans[5001];
int arr[5001] = {1};
int maxLen = 1;

void factorial(int n){
    
    int len = maxLen;
    if(n == 1) arr[0] = 1;
    
    //first calculate by bit
    for(int j = 0; j < len; j++){
        arr[j] *= n;
    }
    
    //整理
    for(int j = 0; j < len; j++){
        if(arr[j] / 10 != 0){
            arr[j+1] += arr[j] / 10;
            if(j == len - 1){
                len++;
                if(len > maxLen) maxLen = len;
            }
        }
        arr[j] = arr[j] % 10;
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
//    std::cout << "Hello, World!\n";
    
    int n = 1;
    cin>>n;
    
    for(int i = 1; i <= n; i++){
        factorial(i);
        
        for(int j = 0; j < maxLen; j++){
            
            ans[j] += arr[j];
            
            if(ans[j] / 10 != 0){
                ans[j+1] += ans[j] / 10;
                ans[j] = ans[j] % 10;
                if(j == maxLen - 1){
                    maxLen++;
                }
            }
            
        }
    }
    
    
    for(int j = maxLen - 1; j >= 0; j--){
        cout << ans[j];
    }
    
    return 0;
}