20241215_1_4_oj

1. 大数阶乘（OJ 版）

题目描述

给定一个正整数 n，计算并输出 n 的阶乘（n!）的值。

输入格式

输入一个正整数 n（1 ≤ n ≤ 1000）。

输出格式

输出一行，为 n! 的准确值，不要有多余的前导 0。

样例输入

5

样例输出

120

数据范围

测试点按照 n 的大小分为三组：

• 第 1-3 点：1 ≤ n ≤ 20
• 第 4-7 点：21 ≤ n ≤ 100
• 第 8-10 点：101 ≤ n ≤ 1000

解析

由于 n! 可能非常大（1000! 约有 2568 位），需要用数组存储每一位。计算过程中：

1. 用数组存储结果的每一位
2. 从 1 乘到 n，每次乘法都需要处理进位
3. 最后倒序输出数组即为结果

答案

#include <stdio.h>

#define MAX_DIGITS 2600  // 1000! 的位数约为 2568

void multiply(int digits[], int n, int* len) {
    int carry = 0;

    for(int i = 0; i < *len; i++) {
        int prod = digits[i] * n + carry;
        digits[i] = prod % 10;
        carry = prod / 10;
    }

    while(carry) {
        digits[*len] = carry % 10;
        carry /= 10;
        (*len)++;
    }
}

int main(void) {
    int n;
    scanf("%d", &n);

    int digits[MAX_DIGITS] = {1};  // 初始值为 1
    int len = 1;

    // 计算阶乘
    for(int i = 2; i <= n; i++) {
        multiply(digits, i, &len);
    }

    // 倒序输出结果
    for(int i = len - 1; i >= 0; i--) {
        printf("%d", digits[i]);
    }
    printf("\n");

    return 0;
}