阶乘和

题意

计算 $S=1!+2!+\cdots+n!$ ，其中 $n\leqslant50$ 。

思路

维护当前 factorial。第 $i$ 轮乘以 $i$ 得到 $i!$ ，再加入 total。Python 的整数会自动扩展，能直接保存阶乘和。

代码

Python代码

python

1
2
3
4
5
6
7
8
9limit = int(input())
factorial = 1
total = 0

for number in range(1, limit + 1):
    factorial *= number
    total += factorial

print(total)

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60/* 高精乘单精 */
/* 高精+高精 */
#include <cstdio>

int a[10000000] = {1};
int b[10000000] = {0};
int len_b = 1;
int cnt = 1;
int n;

void _add(){
    int i,j;
    int _max = len_b;
    if( len_b < cnt)
        _max = cnt;
    for (i=0;i<_max;i++){
        b[i+1] += (b[i]+a[i]) / 10;
        b[i] = (b[i]+a[i]) % 10;
    }
    if( b[_max] != 0)
        len_b = _max+1;
    else
        len_b = _max;

}
void p(){
    int i;
    for(i=cnt-1;i>=0;i--)
        printf("%d",a[i]);
    printf("\n");
    for(i=len_b-1;i>=0;i--)
        printf("%d",b[i]);
    printf("\n");
    printf("\n");
}
int main(){
    scanf("%d",&n);
    int i,j,k;
    for(i=1;i<=n;i++){
        for(j=0;j<cnt;j++){
            a[j] *= i;
        }
        int pre =0;
        for(j=0;j<cnt;j++){
            int t = (a[j] + pre) % 10;
            pre = (a[j] + pre) / 10;
            a[j] = t;
        }
        while( pre != 0){
            a[cnt++] = pre %10;
            pre /=10;
        }

        _add();
        //p();
    }
    for(i=len_b-1;i>=0;i--)
        printf("%d",b[i]);
    return 0;
}

复杂度

循环次数为 $n$ ；实际运行时间还受高精度整数位数增长影响，额外空间为结果所需空间。

总结

阶乘和仍然只需保存一个当前阶乘和一个累计和，无需存储所有阶乘。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结