P1009 阶乘之和
1.为什么要用到高精度？
高精度算法：有时有的数会太大，甚至超过long long的范围
(2^63−1 ≈ 9× 10^18)
此时需要用字符串(string型或char型数组)来存储数字，运算时需要特殊的算法进行运算，称为高精度算法。高精度算法本质上是模拟数字的运算。
2.需要的高精度算法可以分解为加法，乘法((用到加法))，阶乘((用到乘法))，阶乘求和(用到阶乘与加法)。具体如下:
#include
#include
using namespace std;
int num; //输入的数
string ans; //输出的数
//高精度加法
string ADD(string a, string b)
{
string result; //结果
//将较大的数赋值给a，较小的数赋值给b
if(b.length() > a.length())
{
string temp = a;
a = b;
b = temp;
}
int a_len = a.length();
int b_len = b.length();
//b补足零，方便计算
for(int i = 0; i < a_len - b_len; i++)
{
b = '0' + b;
}
int num; //本位
int up = 0; //进位
//模拟加法
for(int i = a_len - 1; i >= 0; i--)
{
int num = (a[i] - '0') + (b[i] - '0') + up;
up = num / 10;
num %= 10;
result = (char)(num + '0') + result;
}
//若仍有进位，加上进位
if(up)
{
result = (char)(up + '0') + result;
}
return result;
}
//高精度乘法
string MUL(string a, string b)
{
string result; //结果
int a_len = a.length();
int b_len = b.length();
int num; //本位
int up = 0; //进位
//模拟乘法
for(int i = a_len - 1; i >= 0; i–)
{
string temp;
for(int j = b_len - 1; j >= 0; j–)
{
num = (a[i] - ‘0’) * (b[j] - ‘0’) + up;
up = num / 10;
num %= 10;
temp = (char)(num + ‘0’) + temp;
}
//若仍有进位，加上进位，记得清零
if(up)
{
temp = (char)(up + ‘0’) + temp;
up = 0;
}
//乘以每位的权重10^k
for(int k = 0; k < (a_len - 1) - i; k++)
{
temp += ‘0’;
}
result = ADD(result, temp);
}
return result;
}
//高精度阶乘
string FAC(int n)
{
string result = “1”;
for(int i = 1; i <= n; i++)
{
//数字转化为字符串
string a;
int temp = i;
while(temp)
{
a = (char)(temp % 10 + '0') + a;
temp /= 10;
}
result = MUL(result, a);
}
return result;
}
int main(void)
{
cin >> num;
for(int i = 1; i <= num; i++)
{
ans = ADD(ans, FAC(i));
}
cout << ans;
return 0;
}
参考：
https://blog.csdn.net/justidle/article/details/104424134?utm_source=app&tdsourcetag=s_pcqq_aiomsg
补一个解法：
#include <bits/stdc++.h>
using namespace std;
int a[10000],k=1,n;
int main()
{
cin>>n;
for(int i=n;i>=1;i–)
{
a[1]++;
for(int j=1;j<=a[0];j++)
{
a[j+1]+=a[j]/10;
a[j]%=10;
}
if(a[a[0]+1]>0)
{
a[0]++;
}
for(int j=1;j<=a[0];j++)
{
a[j]*=i;
}
for(int j=1;j<=a[0];j++)
{
a[j+1]+=a[j]/10;
a[j]%=10;
}
int x=a[0]+1;
if(a[x]>0)
{
while(a[x]>10)
{
a[x+1]=a[x]/10;
a[x]%=10;
x++;
}
a[0]=x;
}
}
for(int i=a[0];i>=1;i–)
{
cout<<a[i];
}
}
这个最精简：
#include
#include
using namespace std;
int n,a[101]={0},s[101]={0};
void change(int x)
{
int g=0;
for(int i=100;i>=0;i–)
{
a[i]=a[i]*x+g;
g=a[i]/10;
a[i]=a[i]%10;
}
}
void qh()
{
int g=0;
for(int i=100;i>=0;i–)
{
s[i]=s[i]+a[i]+g;
g=s[i]/10;
s[i]=s[i]%10;
}
}
void sc()
{
int w;
for(int i=0;i<=100;i++)
{
if(s[i]!=0)
{
w=i;
break;
}
}
for(int i=w;i<=100;i++)
printf("%d",s[i]);
}
int main()
{
scanf("%d",&n);
s[100]=a[100]=1;
for(int i=2;i<=n;i++)
{
change(i);
qh();
}
sc();
return 0;
}
https://www.cnblogs.com/jaszzz/p/12722445.html
剪枝操作