P1009 [NOIP1998 普及组] 阶乘之和

喜欢ヅ旅行 2023-01-12 04:10 98阅读 0赞

## 题目描述 ##

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

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

## 输入格式 ##

一个正整数  n n n。

## 输出格式 ##

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

## 输入 ##

## 输出 ##

## 【数据范围】 ##

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

## 【其他说明】 ##

注，《深入浅出基础篇》中使用本题作为例题，但是其数据范围只有 n \\le 20n≤20，使用书中的代码无法通过本题。

如果希望通过本题，请继续学习第八章高精度的知识。

## 【我建议的参考】 ##

《信息学奥赛课课通》高精度那一章  
《信息学奥赛一本通，C++版》高精度那一章

## 【题解】 ##

思路差不多，看看各位喜欢哪个就用哪个。

#include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    int a[2000];
    int b[2000];
    int c[2000];
    int sum[2000];
    void pplus(int *a, int *c)
    { 
        int jw = 0;
        for (int i = 1; i <= 1000; i++)
        { 
            c[i] += a[i] + jw;
            jw = c[i] / 10;
            c[i] %= 10;
        }
    }
    void cheng(int *a, int c)
    { 
        int jw = 0;
        for (int i = 1; i <= 1000; i++)
        { 
            a[i] = a[i] * c + jw;
            jw = a[i] / 10;
            a[i] %= 10;
        }
    }
    int main()
    { 
        int n;
        cin >> n;
        a[1] = 1;
        for (int i = 1; i <= n; i++)
        { 
            cheng(a, i);
            pplus(a, c);
        }
        bool flag = 0;
        for (int i = 1000; i >= 1; i--)
        { 
            if (c[i] != 0)
                flag = 1;
            if (flag)
                cout << c[i];
        }
    }

这一个的记录是这样的  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70]  
下一个是第二个

#include <iostream>
    #include <stdio.h>
    #include <cstring>
    #include <cstdlib>
    using namespace std;
    int n, h, a[1000];
    int k;
    int anslen;
    int nums[1000], ans[10000], c[1000];
    void cheng(int n);
    void jia()
    { 
        int jw = 0;
        anslen = h;
        for (int i = 1; i <= h; i++)
        { 
            ans[i] += a[i];
            if (ans[i] >= 10)
            { 
                ans[i + 1] += 1;
                ans[i] %= 10;
            }
        }
        while (ans[h + 1] > 0)
        { 
            anslen++;
        }
    }
    void cheng(int n)
    { 
        memset(a, 0, sizeof(a));
        a[1] = 1;
        h = 1;
        for (int i = 2; i <= n; i++)
        { 
            for (int j = 1; j <= h; j++)
            { 
                a[j] *= i;
            }
            for (int j = 1; j <= h; j++)
            { 
                if (a[j] >= 10)
                { 
                    a[j + 1] += a[j] / 10;
                    a[j] %= 10;
                }
            }
            while (a[h + 1] > 0)
            { 
                h++;
                a[h + 1] = a[h] / 10;
                a[h] %= 10;
            }
            if (a[h + 1] > 0)
                h++;
        }
    }
    int main()
    { 
        memset(nums, 0, sizeof(nums));
        memset(ans, 0, sizeof(ans));
        cin >> k;
        for (int x = 1; x <= k; x++)
        { 
            cheng(x);
            // cout << "Factorial : ";
            // for (int i = h; i >= 1; i--)
            // { 
            // cout << a[i];
            // }
            // cout << endl;
            jia();
            // cout << "Current total: ";
            // for (int i = anslen; i >= 1; i--)
            // { 
            // cout << ans[i];
            // }
            // cout << endl;
        }
        for (int i = anslen; i >= 1; i--)
            cout << ans[i];
        cout << endl;
        return 0;
    }

测评  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 1]  
第二个更快

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70]: /images/20221119/88c000eb50a9473d998bf8459a7b9e3f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70 1]: /images/20221119/d582cb33af304f5e82b453436e88cde5.png