P1009 [NOIP1998 普及组] 阶乘之和

题目描述

用高精度计算出 S=1!+2!+3!+⋯+n!（n≤50）。

其中 ! 表示阶乘，定义为 n!=n×(n−1)×(n−2)×⋯×1。例如，5!=5×4×3×2×1=120。

输入格式

一个正整数 n。

输出格式

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

输入输出样例

输入 #1

3

输出 #1

9 

说明/提示

【数据范围】

对于 100%100% 的数据，1≤n≤50。

【其他说明】

NOIP1998 普及组 第二题

需要用高精度——数字超过int甚至是long long类型的数据表示范围，所以可以将数字抽象成整数数组，一位数字就是数组中的一个数字。

在本题中，用两个循环，一个是求阶乘，一个是求和，两个循环中均使用高精度的数据表示方式：先进行正常的相乘或相加，如果出现超过10的数字，注意进一，并自身模10，代码如下。

#include <bits/stdc++.h>
using namespace std;

int main(){
	int i,j,a[1010]={0},b[1010]={0},n;
	cin>>n;
	a[0]=b[0]=1;
	for(i=2;i<=n;i++){
		for(j=0;j<100;j++) b[j]*=i;
		for(j=0;j<100;j++){
			if(b[j]>9){
				b[j+1]+=b[j]/10;//超过10进1
				b[j]%=10;//自身模10
			}
		}
		for(j=0;j<100;j++){
			a[j]+=b[j];
			if(a[j]>9){
				a[j+1]+=a[j]/10;//同上
				a[j]%=10;//同上
			}
		}
	}
	for(i=100;i>=0&&a[i]==0;i--);//找到0的位置，从不是0的地方开始逆向输出
	for(j=i;j>=0;j--) cout<<a[j];
	return 0;
}