阶乘之和

洛谷·深入浅出 · 代码 · cpp · 难度 4/5 · 共 958 字

高精度求 1!+2!+...+n!（n<=50）

洛谷
例题

正文

// 原题：https://oj.yecheng.tv/p/1377
// 题意：求 S = 1!+2!+...+n!，n 可达 50，需用高精度。
// 思路：用小端位数组维护当前阶乘 f 与累加和 s，每次 f*=k、s+=f。
// 复杂度：O(n * 位数)。
// 易错点：50! 远超 long long，必须用高精度；加法进位别漏最高位。
#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int f[120] = {1}, flen = 1;
    int s[120] = {0}, slen = 1;
    for(int k = 1; k <= n; k++){
        int carry = 0;
        for(int i = 0; i < flen; i++){
            int t = f[i] * k + carry;
            f[i] = t % 10;
            carry = t / 10;
        }
        while(carry){ f[flen++] = carry % 10; carry /= 10; }
        carry = 0;
        int mlen = (flen > slen) ? flen : slen;
        for(int i = 0; i < mlen; i++){
            int t = s[i] + (i < flen ? f[i] : 0) + carry;
            s[i] = t % 10;
            carry = t / 10;
        }
        if(carry) s[mlen++] = carry;
        slen = mlen;
    }
    for(int i = slen - 1; i >= 0; i--) cout << s[i];
    cout << endl;
    return 0;
}

阶乘之和

正文

洛谷·深入浅出的其它内容