【题目来源】
https://www.luogu.com.cn/problem/P1729

【题目背景】
《爱与愁的故事第二弹·compute》最终章。
自然对数的底数 e 是一个著名的无理数，其近似值为 2.718281828⋯
有计算 e 的公式：e=1+1/1!+1/2!+1/3!+⋯+1/n!，n∈[0, +∞)。
其中 n! 表示 n 的阶乘，即 n!=1×2×3×⋯×n。

【题目描述】
月落乌啼竟然这么快就回复了圆周率小数点后10000位？！不可能，他肯定求了别人。爱与愁大神再次为难月落乌啼：“帮我算一算 e 后 n(n≤10000) 位，速度！！！”月落乌啼想求别人，结果他发现由于刚才跟你通话已经用完了手机的所有电。关键时刻只能靠自己。如果现在你是他，你会怎么编这个程序？

【输入格式】
只有一行：n。

【输出格式】
若干行。
第一行：2.
第二行开始：e 的小数部分。10 个数一个空格，50 个数一次回车。

【输入样例】
100

【输出样例】
2.
7182818284 5904523536 0287471352 6624977572 4709369995
9574966967 6277240766 3035354759 4571382178 5251664274

【数据范围】
30% 数据：n≤1000
100% 数据：n≤10000

【算法分析】
一、本题不是简单的浮点数计算，因为要求保留小数点后 10000 位小数，double 根本存不下。所以，必须用高精度除法（高精度/低精度）及高精度加法来做。
不过，当保留的小数点位数较小时，可采用如下代码求解。详见“洛谷 B2079：求出 e 的值”：https://blog.csdn.net/hnjzsyjyj/article/details/160158076

#include <bits/stdc++.h>
using namespace std;

int n;
double e=1.0;
double fac=1.0;

int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        fac*=i;
        e+=1.0/fac;
    }
    printf("%.10lf\n",e);

    return 0;
}

/*
in:10
out:2.7182818011
*/

二、高精度除法本质上是将手工除法计算过程程序化。当我们手动计算大数除法时，会逐步处理每一位数字。算法只是将这个过程用程序语言表达出来。很多优秀的算法都源于对基础数学原理的深入理解和巧妙应用。当面对需要处理超大数字的问题时，聪明的程序员会想到将数字按位存储，然后逐位进行数学运算。这种思维方式在计算机科学中非常常见。

三、高精度除法（高精度/低精度）实战推演（以 123456789÷13 为例）
步骤1：数据预处理
○ 将被除数 123456789 以字符串形式读入，转换为数组 a[]=[1,2,3,4,5,6,7,8,9] 存储。
○ 除数 b=13（低精度数）

步骤2：初始化变量
○ 余数变量 r=0（初始余数为 0）
○ 商数组 c=[]（用于存储商的每一位）

步骤3：逐位计算（从左到右）
高精度除法：从被除数的最左位开始处理，每次计算当前被除数 = r × 10 + 当前位数字。
○ 第1位计算：当前被除数=r×10+a=0×10+1=1，商位 c=1÷13=0，新余数 r=1%13=1。
○ 第2位计算：当前被除数=r×10+a=1×10+2=12，商位 c=12÷13=0，新余数 r=12%13=12。
○ 第3位计算：当前被除数=r×10+a=12×10+3=123，商位 c=123÷13=9，新余数 r=123%13=6。
○ 第4位计算：当前被除数=r×10+a=6×10+4=64，商位 c=64÷13=4，新余数 r=64%13=12。
○ 第5位计算：当前被除数=r×10+a=12×10+5=125，商位 c=125÷13=9，新余数 r=125%13=8。
○ 第6位计算：当前被除数=r×10+a=8×10+6=86，商位 c=86÷13=6，新余数 r=86%13=8。
○ 第7位计算：当前被除数=r×10+a=8×10+7=87，商位 c=87÷13=6，新余数 r=87%13=9。
○ 第8位计算：当前被除数=r×10+a=9×10+8=98，商位 c=98÷13=7，新余数 r=98%13=7。
○ 第9位计算：当前被除数=r×10+a=7×10+9=79，商位 c=79÷13=6，新余数 r=79%13=1。

步骤4：结果整理
○ 商数组 c=[0,0,9,4,9,6,6,7,6]
○ 余数 r=1

步骤5：去除前导零
○ 从最高位（最左位）开始去除前导零。去除前导零后商为：[9,4,9,6,6,7,6]。

步骤6：输出商
○ 将商从高位到低位（从左到右）依次输出。商为：9496676

步骤7：验证结果
○ 验证：13×9496676+1=123456788+1=123456789（✓）

整个过程模拟了手工竖式除法，通过数组存储大数，逐位进行除法运算，确保计算精度不受数据类型限制。

四、为什么本题代码中 k<=len 且 len=n+10，而不是 k<=n？
因为，e 的级数需要多算若干项才能让小数位稳定不再变化，len=n+10 就是专门用来提供安全计算位的。否则，会导致最后几位精度丢失、答案错误。例如：
假设要保留 e 的 2 位小数，若：
算到 1/2!：结果 = 1 + 1/1! + 1/2! = 2.50
算到 1/3!：结果 = 1 + 1/1! + 1/2! + 1/3! = 2.66
算到 1/4!：结果 = 1 + 1/1! + 1/2! + 1/3! + 1/4! = 2.70
算到 1/5!：结果 = 1 + 1/1! + 1/2! + 1/3! + 1/4! + 1/5! = 2.71
算到 1/6!：结果 = 1 + 1/1! + 1/2! + 1/3! + 1/4! + 1/5! = 2.71（稳定，不再变）
显然，若想得到正确的 2 位小数，必须多算好几项！

【算法代码】

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin>>n;
    int len=n+10;

    //save the fractional part of e
    vector<int> e(len,0);
    vector<int> fac(len,0); //save 1/k!

    e[0]=1, fac[0]=1;
    for(int k=1; k<=len; k++) { //cal 1/k!
        int rem=0; //remainder
        //High-Precision Division
        for(int i=0; i<len; i++) {
            int t=fac[i]+rem*10;
            fac[i]=t/k;
            rem=t%k;
        }

        //High-Precision Addition
        int carry=0;
        for(int i=len-1; i>=0; i--) {
            e[i]+=fac[i]+carry;
            carry=e[i]/10;
            e[i]%=10;
        }
    }

    //output
    cout<<"2."<<endl;
    for(int i=1; i<=n; i++) {
        cout<<e[i];
        if(i%10==0) cout<<" ";
        if(i%50==0) cout<<endl;
    }
    return 0;
}

/*
in:
1000

out:
2.
7182818284 5904523536 0287471352 6624977572 4709369995
9574966967 6277240766 3035354759 4571382178 5251664274
2746639193 2003059921 8174135966 2904357290 0334295260
5956307381 3232862794 3490763233 8298807531 9525101901
1573834187 9307021540 8914993488 4167509244 7614606680
8226480016 8477411853 7423454424 3710753907 7744992069
5517027618 3860626133 1384583000 7520449338 2656029760
6737113200 7093287091 2744374704 7230696977 2093101416
9283681902 5515108657 4637721112 5238978442 5056953696
7707854499 6996794686 4454905987 9316368892 3009879312
7736178215 4249992295 7635148220 8269895193 6680331825
2886939849 6465105820 9392398294 8879332036 2509443117
3012381970 6841614039 7019837679 3206832823 7646480429
5311802328 7825098194 5581530175 6717361332 0698112509
9618188159 3041690351 5988885193 4580727386 6738589422
8792284998 9208680582 5749279610 4841984443 6346324496
8487560233 6248270419 7862320900 2160990235 3043699418
4914631409 3431738143 6405462531 5209618369 0888707016
7683964243 7814059271 4563549061 3031072085 1038375051
0115747704 1718986106 8739696552 1267154688 9570350354
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/160158076
https://www.luogu.com.cn/problem/solution/P1729
https://www.luogu.com.cn/problem/P1729