文章目录
- 题192.洛谷P1009 模拟-[NOIP1998 普及组] 阶乘之和
- 一、题目
- 二、题解
题192.洛谷P1009 模拟-[NOIP1998 普及组] 阶乘之和
一、题目
二、题解
因为本题n可以很大,所以计算阶乘和之后的结果没办法表示然后输出,所以必须转字符串去模拟计算过程–外壳不变,依旧递归求阶乘,循环求和,其中的用到的起关键作用的求和与求积用模拟竖式计算来解决。代码如下:
#include <bits/stdc++.h>
using namespace std;
string Add(string a,string b)
{
string ans;
int add=0;//需要加到本位的进位数
int i,j;
for(i=a.length()-1,j=b.length()-1;i>=0&&j>=0;i--,j--)
{
int res=(a[i]-'0')+(b[j]-'0')+add;//和等于两数之和加上进位
ans=to_string(res%10)+ans;//只将和的个位数存入结果
add=res/10;//计算进位
}
while(i>=0)
{
int res=(a[i--]-'0')+add;
ans=to_string(res%10)+ans;
add=res/10;
}
while(j>=0)
{
int res=(b[j--]-'0')+add;
ans=to_string(res%10)+ans;
add=res/10;
}
if(add!=0)//如果进位不是0就还得算上
{
ans=to_string(add)+ans;
}
return ans;
}
string Multiple(string a,string b)
{
string tmp[2001];//存储列竖式计算乘法时的中间结果
string ans="0";
if(a[0]==0||b[0]==0)
{
ans="0";
return ans;
}
int alen=a.length(),blen=b.length();
for(int i=blen-1; i>=0; i--)
{
int preadd=0,add=0;//本位的进位,下一位的进位
for(int j=0; j<(blen-1)-i; j++)
{
tmp[i]="0"+tmp[i];//用0补位,便于后序计算
}
for(int j=alen-1; j>=0; j--)
{
int res=(a[j]-'0')*(b[i]-'0');
add+=res/10;//得到下一位进位
res=res%10;//本位结果只留个位数
res+=preadd;//本位结果还需加上本位的进位
add+=res/10;//本位结果又做了加法所以得再更新一回下一位进位
res=res%10;
preadd=add;//更新本位的进位,给下一轮使用
add=0;//下一位进位再初始化为0
tmp[i]=to_string(res)+tmp[i];
}
if(preadd!=0)//如果进位不是0就还得算上
{
tmp[i]=to_string(preadd)+tmp[i];
}
ans=Add(ans,tmp[i]);
}
return ans;
}
string getFactorial(int n)
{
if(n==1)
{
return "1";//原本为1
}
else
{
return Multiple(to_string(n),getFactorial(n-1));//原本为n*getF...(n-1)
}
}
int main()
{
int n;
cin>>n;
string res="0";
for(int i=1;i<=n;i++)
{
res=Add(res,getFactorial(i));
}
cout<<res<<endl;
}