博客

题目详情


15:阶乘和

查看 提交 统计 提问

总时间限制: 1000ms 内存限制: 65536kB

描述

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

其中“!”表示阶乘，例如：5!=5*4*3*2*1。

输入正整数N，输出计算结果S。

输入

一个正整数N。

输出

计算结果S。

样例输入

5

样例输出

153

来源

NOIP1998复赛 普及组 第二题

高精度的主要思想就是用多个数组来存数字，读入用字符串。

然后转成一位一个数组的整数数组。

但是这题并不需要读入，于是我们可以节约一点空间，

一个数组存5位（如果你喜欢，存更多位也可以，不过不能超int）

#include<iostream>
#include<cstdio>
using namespace std;
int a[39900];
int x;
int j,n;
void pig(int f)
{
    for(int i=0;i<=x;i++)
    {
        if(a[i]>=100000)
        {
            a[i+1]+=a[i]/100000;
            a[i]=a[i]%100000;
            if(i==x)
            x++;
        }
        a[i]*=f;
    }
    a[0]+=f;//若f(n)=n!+（n-1）！+...+1！，则有(n+1)!=f(n)*n+n=(f(n)+1)*n.
}
int main()
{
    scanf("%d",&a[0]);
    for(int y=a[0]-1;y>=1;y--)
    {
        pig(y);
    }
    for(int i=0;i<=x;i++)
    {
        if(a[i]>=100000)
        {
            a[i+1]+=a[i]/100000;
            a[i]=a[i]%100000;
            if(i==x)
            x++;
        }
    }
    for(int i=x+1;i>=0;i--)//不可能超过x+1位。
    {
        if(a[i])
        {
            printf("%d",a[i]);//没有前导0
            for(i--;i>=0;i--)
            {
                printf("%.5d",a[i]);//后面得5位的输出，没有就前面补0.
            }
        }
    }
}

另外，我是不会给完代码就走人的，这题还可以用重载运算符：


重载运算符