题解：P12323 [蓝桥杯 2023 省 Java B] 阶乘求和

· · 题解

题意 & 化简

这道题要我们求，从 1 的阶乘一直加到 202320232023。

思路 1.0

这道题数据非常大，所以我们考虑高精度，用 1998 年普及组阶乘之和的做法，来写此题，数组开到 10 ^ 8 差不多就够了。

思路 2.0

高精度也许能过此题，但是极其麻烦，甚至还有超时的风险，所以，我们要想一种方法来解决。

首先，为了使计算量少，我们肯定希望 2 和 5 越多越好，这样 0 就越多。

于是，我们可以贪心一下，我们希望的是有一个数的阶乘，后面 9 位都是 0，而且，某个数后九位是 0，比他大的数的阶乘不会后九位不是 0。所以，我们只要先求出最小的、后九位是 0 数即可。

在纸上求质因数发现，只要到 40 的阶乘所产生的 0 就大于 9 了，因为 40 的阶乘所相乘的每一个数字分解质因数后 2 和 5 都严格大于等于 9 个。

所以，我们可以枚举 1 到 39，来记录阶乘的和，并且要在过程中取模 10 ^ 9。

代码：

#include<bits/stdc++.h>
using namespace std;
long long ans,f = 1;
const long long P = 1e9;
int main(){
    for (int i = 1;i <= 39;i++){
        f = (f * i) % P;// 这里有个小技巧，每一个阶乘都是前一个乘i，这样还省了一个log时间复杂度。
        ans += f;
        ans %= P;
    }
    printf("%lld\n",ans);
}

思路 3.0

这道题我们可以手算，只要不嫌麻烦，可以根据上面的思路来一步一步计算，只要不算错，就可以了，算出来取模 10 ^ 9 的结果为 420940313。

代码：

#include<bits/stdc++.h>
int main(){printf("420940313");}