P1009 [NOIP1998 普及组] 阶乘之和

题目描述

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

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

输入格式

一个正整数 nn。

输出格式

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

输入输出样例

3

9

说明/提示

【数据范围】

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

解题思路

阶乘数值较大，c++难以支持，采用高精度算法来实现

高精度乘法:

void multiple(int x){
int g=0;//进位
for(int i=100;i>=0;i--){
a[i]=a[i] * x + g;
g = a[i]/10;
a[i] = a[i] % 10;

}
}

高精度加法

void add(){
int g=0;//进位
for(int i=100;i>=0;i--){
s[i]=a[i] + s[i] + g;
g = s[i]/10;
s[i] = s[i] % 10;

}
}

完整实现：

#include<iostream>
#include<cstdio>
using namespace std;
int n,a[101]={0},s[101]={0};
void change(int x)
{
    int g=0;
    for(int i=100;i>=0;i--)
    {
        a[i]=a[i]*x+g;
        g=a[i]/10;
        a[i]=a[i]%10;
    }
}
void qh()
{
    int g=0;
    for(int i=100;i>=0;i--)
    {
        s[i]=s[i]+a[i]+g;
        g=s[i]/10;
        s[i]=s[i]%10;
    }
}
void sc()
{
    int w;
    for(int i=0;i<=100;i++)
    {
        if(s[i]!=0)
        {
            w=i;
            break;
        }
    }
    for(int i=w;i<=100;i++)
       printf("%d",s[i]);
}
int main()
{
    scanf("%d",&n);
    s[100]=a[100]=1;
    for(int i=2;i<=n;i++)
    {
        change(i);
        qh();
    }
    sc();
    return 0;
}