题目链接:https://www.luogu.com.cn/problem/P1009
思路:计算阶乘相当于大整数
1
1
1 依次乘以
1
∼
n
1 \sim n
1∼n,累加阶乘相当于大整数
0
0
0 依次和大整数
1
!
∼
n
!
1! \sim n!
1!∼n! 相加。因此,直接复用 高精度乘低精度 和 高精度加高精度 的代码即可。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> add(vector<int> &a, vector<int> &b)
{
// 保证a.size() >= b.size()
if (a.size() < b.size())
{
return add(b, a);
}
vector<int> c;
int t = 0;
for (int i = 0; i < a.size(); i++)
{
// 逐位相加
t += a[i];
if (i < b.size())
{
t += b[i];
}
c.push_back(t % 10);
t /= 10; // 向高位进位
}
// 如果最高位还有进位
if (t)
{
c.push_back(t);
}
return c;
}
vector<int> mul(vector<int> &a, int b)
{
vector<int> c;
for (int i = 0, t = 0; i < a.size() || t; i++)
{
if (i < a.size())
{
t += a[i] * b;
}
c.push_back(t % 10);
t /= 10;
}
// 删除前导0
while (c.size() > 1 && c.back() == 0)
{
c.pop_back();
}
return c;
}
int main()
{
int n;
cin >> n;
vector<int> fac, sum;
fac.push_back(1);
sum.push_back(0);
for (int i = 1; i <= n; i++)
{
fac = mul(fac, i);
sum = add(sum, fac);
}
for (int i = sum.size() - 1; i >= 0; i--)
{
cout << sum[i];
}
cout << endl;
return 0;
}