题目分析

本题要求计算 $n!$ 的最后一位非零数字，其中 $n$ 可达 $10^{100}$，无法直接计算阶乘。

---

数学原理

末尾零的产生

$n!$ 末尾的零来自因子 $2$ 和 $5$ 的配对。由于 $2$ 的个数多于 $5$，末尾零的个数由 $5$ 的因子个数决定。

最后非零数字的计算

去掉所有 $2$ 和 $5$ 的因子对后，剩余因子的乘积的个位数即为所求。

已知结论：设 $L(n)$ 为 $n!$ 的最后非零数字，则：

$$L(n) = L\left(\left\lfloor \frac{n}{5} \right\rfloor\right) \times L(n \bmod 5) \times 2^{\lfloor n/5 \rfloor} \bmod 10 $$

其中 $L(0)=1$，$L(1)=1$，$L(2)=2$，$L(3)=6$，$L(4)=4$。

---

代码解析

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

char s[100005];
int n, a[100005];
// 预处理的查找表：f[k] = L(n) 对于 n=0 到 19
int f[32] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8, 4, 4, 8, 4, 6, 8, 8, 6, 8, 2};
int ans;

int main() {
    for (int i = 1; i <= 5; i++) {
        ans = 1;
        scanf("%s", s);
        n = strlen(s);
        
        // 将字符串转换为大整数数组（逆序存储）
        for (int i = 0; i < n; i++)
            a[n - i - 1] = s[i] - '0';
        
        // 循环处理，每次相当于 n = n/5
        while (n > 1) {
            // 去除前导零
            while (a[n - 1] == 0)
                n--;
            
            // 计算 L(n mod 20) × 2^(n/5) mod 10
            // a[1]%2*10 + a[0] 相当于 n mod 20
            ans = ans * f[a[1] % 2 * 10 + a[0]] % 10;
            
            // 计算 n/5（大整数除以5）
            int x = 0;
            for (int j = n - 1; j >= 0; j--) {
                x = x * 10 + a[j];
                a[j] = x / 5;
                x %= 5;
            }
        }
        
        // 最终结果：ans × L(n) mod 10，其中n此时小于5
        printf("%d\n", ans * f[a[0]] % 10);
    }
    return 0;
}

---

预处理表说明

f[0..19] 存储了 $n!$ 的最后非零数字：

• $f[0] = L(0) = 1$
• $f[1] = L(1) = 1$
• $f[2] = L(2) = 2$
• $f[3] = L(3) = 6$
• $f[4] = L(4) = 4$
• $f[5] = L(5) = 2$
• ...
• $f[19] = L(19) = 2$

实际上 $f[k] = L(k)$ 对于 $k=0$ 到 $19$。

---

算法流程

1. 输入处理：将 $n$ 作为字符串读入，转换为大整数数组（逆序存储）
2. 循环计算：
   • 去除大整数前导零
   • 计算 $L(n \bmod 20) \times 2^{\lfloor n/5 \rfloor} \bmod 10$ 并累积到答案
   • 将 $n$ 除以 $5$ 继续下一轮
3. 终止条件：当 $n < 5$ 时，直接查表得到 $L(n)$
4. 输出结果：所有累积结果的乘积模 $10$

---

关键步骤详解

大整数处理

• 数组 a 逆序存储数字，a[0] 是个位，a[1] 是十位，依此类推
• 大整数除以 $5$ 通过模拟竖式除法实现

核心计算公式

在循环中执行的实际上是：

$$\text{ans} = \text{ans} \times L(n \bmod 20) \times 2^{\lfloor n/5 \rfloor} \bmod 10 $$

其中 $2^{\lfloor n/5 \rfloor}$ 的个位数通过预处理表隐含处理。

---

复杂度分析

• 时间复杂度：$O(\log_5 n)$ 每次循环 $n$ 除以 $5$，循环次数为 $n$ 的 $5$ 进制位数
• 空间复杂度：$O(\log_{10} n)$ 存储大整数数组

---

示例验证

$n=15$ 的计算过程：

1. 初始：$n=15$，ans=1
2. 第一轮：$n \bmod 20 = 15$，$f[15]=8$，ans=1×8=8 $n = 15/5 = 3$
3. 第二轮：$n=3<5$，循环结束
4. 最终：ans × f[3] = 8 × 6 = 48 → 8

输出 $8$，与样例一致。

---

算法优势

• 高效处理大数：避免直接计算阶乘，适用于 $n$ 极大的情况
• 数学优化：利用模运算和预处理表加速计算
• 正确性保证：基于严格的数论公式推导

该解法充分利用了阶乘最后非零数字的数学性质，通过递归分解和预处理技术，实现了对大数情况的高效计算。