题解 | 阶乘之和-牛客假日团队赛8C题
C-阶乘之和_牛客假日团队赛8
https://ac.nowcoder.com/acm/contest/1069/C
题目描述
用高精度计算出输入描述:
输入正整数N
输出描述:
输出计算结果S
示例1
输入
3
输出
9
解答
本题可以用高精度暴力求解，但代码量过大。我们在这里有一种优化的思路。
由于!%20%2B%20(n%20-%202)!%20%2B%20..%20%2B%202!%20%2B%201!%20%3D%20(..((((0%20%2B%201)%20%5Ctimes%20n%20%2B%201)%20%5Ctimes(n%20-%201)%20%2B%201)%20%5Ctimes(n%20-%202)%20%2B%201)%5Ctimes%20..%20%5Ctimes%202%20%2B%201)%5Ctimes%201)
，所以我们可以得出以下算法：
第一步：令
，读入 
；
第二步：令%5Ctimes%20n)
，令
；
第三步：判断是否
，若是则转第二步，若否则转第四步；
第四步：输出
。
将以上算法套入高精度，即为本题的优化算法。
代码如下：
经过以上优化，我们可以发现，相对于朴素算法而言，我们已经省去了一个高加高的过程，并节省了一个高精度数组。更为重要的是，我们压缩了代码量，使之更易编写和调试。
由于本题数据过弱，所以不需要高精度快速幂)
的算法，只需要朴素的 )
的算法便足以通过。
来源：Foliciatarier
由于
第一步：令
第二步：令
第三步：判断是否
第四步：输出
将以上算法套入高精度，即为本题的优化算法。
代码如下：
#include"stdio.h"
#include"string.h"
int answer[20];
int main()
{
int m,n;
scanf("%d",&n);
memset(answer,0,sizeof(answer));
answer[m=0]=n;
while(--n)
{
answer[0]++;
for(int i=0;i<=m;i++)
answer[i]*=n;
for(int i=0;i<=m;i++)
answer[i+1]+=answer[i]/10000,
answer[i]%=10000;
if(answer[m+1]>0)
m++;
}
printf("%d",answer[m--]);
while(m>=0)
printf("%04d",answer[m--]);
return 0;
} 为了方便起见，作者的代码采用了万进制的优化方法。经过以上优化，我们可以发现，相对于朴素算法而言，我们已经省去了一个高加高的过程，并节省了一个高精度数组。更为重要的是，我们压缩了代码量，使之更易编写和调试。
由于本题数据过弱，所以不需要高精度快速幂
来源：Foliciatarier
