洛谷P1009阶乘之和

1. 题目描述

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

其中“!”表示阶乘,例如:$5!=5×4×3×2×1$。

2. Notes

2.1. 思路

题目是给定一个$n$,让求从$n$的阶乘加到$1$的阶乘,考虑到$n!=n*(n-1)!$,我们可以先从1的阶乘开始算起,这样计算下一个阶乘的时候,前面计算出的阶乘可以直接拿来用。

因此,算法的思路就是先用高精乘计算出从1到n每个数的阶乘,然后将其存到string数组中,每一个单位存一个阶乘。然后再利用高精加对他们求和。

2.2. 犯错的点

  1. 高精加的时候,对string类+的重载拼接字符串不是太搞得明白,有时候会抽风,建议还是append()吧。
  2. 高精乘$a*b$的时候,记得考虑$b$的每一位都与$a$乘完后可能有进位,另外记得除去开头多余的0。

2.3. 经验点

做循环的时候,虽然要考虑循环中的一般情况,但也要考虑好循环开始和结束的位置的特殊情况,注意每一个能注意到的细节。

3. 代码

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;
void add(string&a,string b); //结果保存在第一位
void multiply(string&a,string b); //结果保存在第一位
int main(){
int N,i,j;
string result("0");
string tmp;
string sv[52];
sv[0]="1";
cin>>N;
//先获得所有的阶乘
for(i=1;i<=N;i++){
tmp="";
j=i;
while(j){
tmp=tmp+(char)((j%10)+'0');
j/=10;
}
reverse(tmp.begin(),tmp.end());

multiply(tmp,sv[i-1]);
sv[i]=tmp;
}
//再相加
for(i=2;i<=N;i++){
add(sv[1],sv[i]);
}
cout<<sv[1];
}

void add(string&a,string b){
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
int m = a.length();
int n = b.length();
int i,tmp,carry=0;
if(m<n){
for(i=0;i<n-m;i++){
a=a+'0';
}
}else{
for(i=0;i<m-n;i++){
b=b+'0';
}
n=m;
}
for(i=0;i<n;i++){
tmp=a[i]-'0'+b[i]-'0'+carry;
carry=tmp/10;
a[i]=(char)(tmp%10+'0');
}
if(carry>0){
a.append("1");
}
reverse(a.begin(),a.end());
}

void multiply(string&a,string b){
if(a[0]=='0' or b[0]=='0'){
a='0';
}else{
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
int m = a.length();
int n = b.length();
string sv[n];
int i,j,k,tmp,carry=0;
for(i=0;i<n;i++){
carry=0;
for(j=0;j<m;j++){
tmp=(a[j]-'0')*(b[i]-'0')+carry;
sv[i]=sv[i]+(char)((tmp%10)+'0');
carry=tmp/10;
}
if(carry>0){
sv[i]=sv[i]+(char)(carry+'0');
}
for(k=0;k<i;k++){
sv[i]='0'+sv[i];
}
reverse(sv[i].begin(),sv[i].end());
}
for(i=1;i<n;i++){
add(sv[0],sv[i]);
}
a=sv[0];
}
}