c++ - What is the principle of this high-precision factorial operation?

Question

#include <iostream>
#include <string.h>
#include <stdio.h> 
using namespace std;
const int max=3000;
int f[3000];
int main()
{ 
    int i,j,n;
    scanf("%d",&n);
    memset(f,0,sizeof(f));
    f[0]=1;
    for(i=2;i<=n;i++)            //从i乘到n 
    {
        int c=0;
        for(j=0;j<3000;j++)     //每一位在乘法时的调整 
        {
            int s=f[j]*i+c;     
            f[j]=s%10;
            c=s/10;
        }
    }
    for(j=3000-1;j>=0;j--)              
    if(f[j]) break;
    for(i=j;i>=0;i--)
    cout<<f[i];
    
     
        return 0;
}

I want to write a comment to help myself understand, but I can’t continue writing halfway through. Why are the three lines in the middle of for written like that?

Answer 1

It seems to be just an ordinary vertical calculation of multiplication, there’s nothing much to say

Answer 2

#include <iostream>
#include <string.h>
#include <stdio.h> 
using namespace std;
const int maxn = 3000;//3000意指结果最多含3000个数字
int f[maxn];//结果存储器.下标大的元素对应结果的高位.即f[0]对应结果的个位.
//每次运行,f[]的每个元素初始值都是0.
//这里为了便于理解修改成了maxn,且避免与<algorithm>以及<cmath>库中的同名函数重复.
int main()
{ 
    //初始化开始
    int i,j,n;
    scanf("%d",&n);
    f[0]=1;
    //memset(f,0,sizeof(f)); //f声明在main外头,初始值都为0,不需要memset
    //初始化结束

    //开始计算阶乘
    for(i=2;i<=n;i++)//从2乘到n.
    {
        int c=0;//进位存储器.
        for(j=0;j<maxn;j++)//每一位都乘个i.
        {
            int s=f[j]*i+c;//f[j]是当前被乘i的那一位上的数字,"+c"是进位;s的值最大是9*9=81,最小是0,不会超过两位数
            f[j]=s%10;//模10,意在取计算结果个位上的数字,赋值给f[j]
            c=s/10;//除10,意在取十位上数字.
            //若无十位上的数字,则c为0;因为c++中,整型除法向0取整(理解起来等价于舍去小数部分),如9/10=0;
        }
    }
    //计算结束

    //输出开始
    for(j=maxn-1;j>=0;j--)              
        if(f[j]) break;
    for(i=j;i>=0;i--)
        cout<<f[i];
        /*这两句的意思很简单，假设f[]是这样的：(这边是f[2999]->)0000000...(省略若干个0)...00123123123(<-f[0]在这边)
         *先从高位开始往低位找，找到第一个不为零的数字，记下标为j,
         *然后再从j到0依次输出f[]中每一位的值
         */

    //输出结束
    return 0;
}

Answer 3

Since multiplication will exceed int or even long long, high precision is required.
The idea of ​​high precision is to use an array to store each digit of the number, and then simulate the vertical multiplication method of human calculation of multiplication.
You can consider how to calculate an array a of length n times a number x, assuming that a is stored from low to high (for example, the number 12345, the array is a[1]=5,a[2]=4,a [3]=3,a[4]=2,a[5]=1).
First of all, everyone is a[1]x%10, but what is the tens digit? It should be (a[2]x+carry of the previous digit)%10
So here, c represents the carry of the previous digit. , f[j] represents the j-th bit of (i-1)! before looping to j, and after looping to j, it represents the j-th bit of i!.