题面

简单n!
Time Limit: 1000MS Memory limit: 65536K

题目描述
给定一个数n（0 <= n <=150）, 求0到n中所有数的阶乘。

输入
题目有多组数据，处理到文件结尾。输入一个数n。

输出
输出阶乘，形式如：4! = 24.每组数据输出后跟一个空行。

示例输入
1 4

示例输出
0! = 1 1! = 1

0! = 1 1! = 1 2! = 2 3! = 6 4! = 24

解题思路

注意到题目中给出的 n 最大值是 150，显然其阶乘用 int 和 long long 都是存不下的，需要模拟能存放大数的数据类型，容易想到的方法是定义一个 int 型数组 a, 每个元素存储大数的每一位数字。但是每一个元素仅存储一位数字显然有些浪费，并且在运算中做乘法运算时，每一位数字都参与运算一次，当大数的位数较大时循环次数会比较多。因此，我们不妨让每个元素记录 4 位数字。例如：对于一个大数 12345678987，我们从后向前每 4 位数记录到数组 a 的一个元素中，即 a[0] = 8987, a[1] = 4567, a[2] = 123。在输出时按下标从后向前输出即可表示大数。

解决了如何存储大数的问题，剩下的就是如何做乘法了。容易想到的思路是模拟手算竖式乘法，但是稍有不同的是我们将每 4 位数存储到一个数组元素中当作一位，所以我们的进位设定为逢万进一。例如：

_36230
x____8
289840

对于 36230 x 8 ，我们的被乘数是 36230，即 a[0] = 6230, a[1] = 3，乘数是8。和传统竖式乘法不同的是，我们每 4 位数做一次运算，即首先运算 6230 x 8 = 49840，逢万进一，进位为 4，进位后 a[0] 为 9840。之后计算下一个位，3 x 8 = 24，加上进位为 a[1] = 24 + 4 = 28，进位为 0。至此 a 中元素全部运算完毕，按数组下标逆序输出即为结果 289840。

这样我们就可以写出本题的代码了：

#include <stdio.h>

int main(int argc, char const *argv[])
{
    //数组a的大小能存下150!(200多位的数)即可
    //len表示当前大数的长度
    //carry表示进位数
    //product表示当前位做乘法运算后的乘积
    int a[66], n, len, carry, product, i, j;
    while(~ scanf("%d", &n))
    {
        printf("0! = 1\n");
        len = 1;
        a[0] = 1;
        for(i=1; i<=n; ++i)
        {
            carry = 0;
            for(j=0; j<len; ++j)
            {
                //计算当前位的乘积
                product = a[j]*i + carry;
                //进位后的值通过乘积取余10000得到
                a[j] = product % 10000;
                //进位数通过乘积/10000得到
                carry = product / 10000;
            }
            a[j] = carry;
            //计算完毕后如果存在进位，则长度+1
            if(carry) len++;
            printf("%d! = %d", i, a[len-1]);
            for(j=len-2; j>=0; --j)
            {
                //不足四位数的前补0来输出
                printf("%04d", a[j]);
            }
            printf("\n");
        }
        printf("\n");
    }
    
    return 0;
}

其他解题方法

其实运用 Java 的 BigInteger 可以方便的处理大数运算，具体关于 BigInteger 的用法可以自行去搜索。在这里只提供代码：

import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        BigInteger a;
        int n;
        while(in.hasNext()) {
            n = in.nextInt();
            a = BigInteger.ONE;
            System.out.println(0 + "! = " + 1);
            for(int i=1; i<=n; ++i) {
                a = a.multiply(BigInteger.valueOf(i));
                System.out.println(i + "! = " + a);
            }
            System.out.println();
        }
    }
}