23. N 的阶乘Ⅱ

题目描述

输入一个正整数N，输出N的阶乘。

输入描述:

正整数N(0<=N<=1000)

输出描述:

输入可能包括多组数据，对于每一组输入数据，输出N的阶乘

示例1

输入

4
5
15

输出

24
120
1307674368000

思路

这题相对于前面那一题阶乘，数据规模扩大了，为 1000 以内的正整数，所以只能用数组存数，于是想到把数组的每一位当作万进制的每一位，之所以选用万进制，是因为最大值 1000 乘以一万也不会溢出 int，如果数据规模给的是100000以内，那么可以选择千进制，保证 int 不溢出

解法

#include <stdio.h>

void factorial(int N) {
    int a[1001] = {0};    //使用万进制，数组的每个值当作万进制的一位，则每个数组位可以存4位数，最大可以存4004位数，如果还不够，可以再加
    int tag = 1;    //下方控制输出用得到
    a[1000] = 1;    //由于是倒着存，便于正着输出，所以初始最后一个数组为 1
    for (int i = 1; i <= N; i++) {    //待求阶乘的数遍历一遍
        for(int k = 0; k < 1001; k++)    //由于进位规则是先乘再进位，所以先把每一位都乘 i，下面再处理进位
            a[k] *= i;
        for(int j = 1000; j >=0; j--){    //大于一万的进位
            if (a[j] > 10000) {
                a[j - 1] += a[j] / 10000;
                a[j] %=10000;
            } 
        }
    }
    for (int i = 0; i < 1001; i++) {    //每位数组够四位直接输出，不够则前面补零
        if (!tag) {    //tag 改变则说明已经不是第一个数了，则需要补零
            if (a[i] >= 1000)
                printf("%d", a[i]);
            else if (a[i] >= 100)
                printf("0%d", a[i]);
            else if (a[i] >= 10)
                printf("00%d", a[i]);
            else
                printf("000%d", a[i]);
        }
        if (a[i] != 0 && tag) {    //第一个数不用补零，tag 用来记录第一个数
            printf("%d", a[i]);
            tag = 0;
        }
    }
    printf("\n");
}

int main() {
    for(int N; ~scanf("%d", &N);)
        factorial(N);
    return 0;
}