洛谷题解P1009 阶乘之和

实现代码：

#include<iostream>
using namespace std;

int a[2000];
int c[2000];
const int maxDigit=1000; //最大位数，调试时可设n=4,maxDigit=3

// 阶乘相加
void add(int *a,int *c)
{
    int carry = 0;
    // 比如1!+2!+3!+4!
    // i=1时，c[1]=1!=1
    // i=2时，c[1]=1+2!=3
    // i=3时，c[1]=3+3!=9
    // i=4时，c[1]=9+4=13,carry=1,c[1]=3,c[2]=c[2]+a[2]+carry=0+2+1=3
    for(int i = 1; i <= maxDigit; i++)
    {
        c[i] += (a[i] + carry);
        carry = c[i]/10;
        c[i] %= 10;
    }
}

//求阶乘
void fact(int *a,int num)
{
    int carry = 0; // 进位
    for(int i=1; i <= maxDigit; i++)
    {
        // 从高位往低位存储数据，比如5!=120,则a[4]=a[5]=...=0,a[3]=1,a[2]=2,a[1]=0
        a[i] = a[i] * num + carry;
        carry = a[i] / 10;
        a[i] %= 10;
    }
}

int main()
{
    int n;
    cin >> n;
    a[1] = 1;
    for(int i=1;i<=n;i++)
    {
        fact(a, i);
        add(a, c);
    }

    bool flag = false; // 当碰到第一个非0时，更新为true
    for(int i = 1000; i >= 1; i--)
    {
        // 左边的0不要打印出来，从第一个非0数字开始打印
        // 比如000……000120，打印出120
        if(c[i] != 0)
        {
            flag = true;
        }

        if(flag)
        {
            cout << c[i];
        }
    }

    return 0;
}

少儿编程、算法咨询请加微信307591841或QQ群581357582

信息学竞赛公众号.jpg