P1729 计算e
题目背景
《爱与愁的故事第二弹·compute》最终章。
自然对数的底数 \(e\) 是一个著名的无理数，其近似值为 \(2.718281828\cdots\) 有计算 \(e\) 的公式如下：
\[e=\sum_{n=0}^{\infty}\frac{1}{n!} \]其中 \(n!\) 表示 \(n\) 的阶乘，即 \(n!=1\times 2\times 3\times \cdots \times n\)。
题目描述
月落乌啼竟然这么快就回复了圆周率小数点后10000位？！不可能，他肯定求了别人。爱与愁大神再次为难月落乌啼：“帮我算一算 \(e\) 后 \(n(n \le 10000)\) 位，速度！！！”月落乌啼想求别人，结果他发现由于刚才跟你通话已经用完了手机的所有电。关键时刻只能靠自己。如果现在你是他，你会怎么编这个程序？
输入格式
只有一行：\(n\)
输出格式
若干行。
第一行：\(2\).
第二行开始：\(e\) 的小数部分。\(10\) 个数一个空格，\(50\) 个数一次回车。
样例
输入
100
输出
2.
7182818284 5904523536 0287471352 6624977572 4709369995
9574966967 6277240766 3035354759 4571382178 5251664274
提示
\(30\%\) 数据：\(n \le 1000\)
\(100\%\) 数据：\(n \le 10000\)
时限：全部1秒
思路
\(e\) 是一个无理数，要求求出小数点后 \(10000\) 位。观察公式可看出：\(e\) 的值由“\(\dfrac{1}{n!}\)”的值进行累加，其中 \(n\) 是 \(0\) 到 \(10000\) 的整数，累加的过程可以用循环实现。可以想到，当上一步“\(\dfrac{1}{(n-1)!}\)”已经被计算出来，再除以 \(n\)，即可得到“\(\dfrac{1}{n!}\)”的值。
将上述思路整理后，得到以下方法：
- 由公式得出 \(\dfrac{1}{0!}=1,\dfrac{1}{1!}=1,\dfrac{1}{2!}=0.5\)。\(e\) 的整数位“\(2.0\)”可以直接输出。然后从 \(3\) 开始枚举，使用高精度除法得到“\(0.5\) 除以 \(3\)”的值，将该值运用高精度加法累加到答案中，以此类推，直到循环至 \(n\) 结束。
- 由于要得到小数点后 \(10000\) 位，因此高精度算法枚举每一位运算，需要枚举 \(10000\) 位。而计算“\(\dfrac{1}{n!}\)”这一步，\(n\) 也需要枚举到 \(10000\)，加上代码中其他常数，时间复杂度超过 \(10^8\)。为了降低时间复杂度，考虑压位高精度，位数的枚举也从原来的 \(10000\) 位降到 \(1250\) 位（代码为了保证精度多枚举了 \(5\) 位），时间复杂度降为原来的 \(\dfrac{1}{8}\)。
- 这里采用了“压 \(8\) 位”的方式。由于输出方式位“\(10\) 个数一个空格，\(50\) 个数一次回车”，需要将之前压 \(8\) 位的数字进行整数分离，输出的时候统计输出数字的数量，当累计到 \(10\) 个数字的时候输出空格，\(50\) 个数字的时候换行。
代码
#include <bits/stdc++.h>
#define base 100000000
using namespace std;
const int n = 10000;
long long a[1255], c[1255], x;
int t, len, sum, ans[20];
int main()
{
a[1] = 5;
scanf("%d", &len);
if (n >= 1)
printf("2.\n");
if (n >= 2)
c[1] = 5; // c[1] 只存放一位数，数组 c 的其他位都存放 8 位数
for (int i = 3; i <= n; i ++ )
{
long long x = 0;
for (int j = 1; j <= 1255; j ++ ) // 高精度除法
{
x = x * base + a[j];
a[j] = x / i;
x %= i;
}
for (int k = 1255; k >= 1; k -- ) // 高精度乘法
{
c[k] += a[k];
c[k - 1] += c[k] / base;
c[k] = c[k] % base;
}
}
printf("%lld", c[1]); // c[1] 只存放一位数，sum ++
sum ++; // sum 统计数字个数
for (int i = 2; sum <= len - 1; i ++ ) // 对每个万进制数整数分离，拆成 8 个一位数
{
int p = 8;
while (c[i])
{
ans[p --] = c[i] % 10;
c[i] /= 10;
}
for (int j = 1; j <= 8 && sum < len; j ++ ) // 每 50 个换行，每 10 个空格
{
printf("%d", ans[j]);
sum ++;
if (sum % 50 == 0)
printf("\n");
else if (sum % 10 == 0)
printf (" ");
}
for (int j = 1; j <= 8; j ++ )
ans[j] = 0;
}
return 0;
}