P1604. Just the Facts 题解

一、题目分析

计算 ( N! ) 的最后一个非零数字。直接计算阶乘会导致数值过大，因此需要通过数学方法避免大数运算，同时去除末尾的零并保留足够的有效数字以确定最后一位非零数。

二、解题思路

关键观察

1. 末尾零的来源：末尾的零由因子 ( 2 \times 5 ) 产生。每对 ( (2, 5) ) 贡献一个零，而 ( N! ) 中因子 2 的数量远多于 5，因此只需统计因子 5 的数量，并匹配相应的因子 2 来消除零。
2. 周期性规律：对于较大的 ( N )，阶乘的末尾非零数字呈现周期性，可以利用模运算和周期性简化计算。

优化方法

1. 去除末尾零：在计算阶乘时，每次乘法后立即除以 10 的因子（即去除末尾的零）。
2. 模运算保留有效数字：由于只需最后一位非零数字，保留足够的低位数字（如模 ( 10^5 )）即可避免数值溢出，同时确保计算的准确性。

三、代码实现

#include<iostream>
#include<cstdio>
#define MOD 100000 // 保留最后5位有效数字，确保去除零后仍能正确计算末位
using namespace std;

int main() {
    int n;
    while (~scanf("%d", &n)) {
        if (n == 0) {
            printf("    0 -> 1\n"); // 特殊情况：0! = 1
            continue;
        }

        int result = 1; // 存储当前乘积的有效部分（去除末尾零后）
        for (int i = 1; i <= n; i++) {
            result *= i;
            // 去除末尾的零
            while (result % 10 == 0) {
                result /= 10;
            }
            // 取模避免数值过大，保留足够的有效数字
            result %= MOD;
        }

        // 输出结果，右对齐占5列，最后一位非零数字
        printf("%5d -> %d\n", n, result % 10);
    }
    return 0;
}

四、代码解析

1. 输入处理：循环读取输入的 ( N )，处理 ( N=0 ) 的特殊情况（直接输出 1）。
2. 阶乘计算：
   • 初始化 result 为 1，逐次乘以 ( 1 ) 到 ( N )。
   • 每次乘法后，通过循环除以 10 去除末尾的零，确保 result 末尾非零。
   • 对 result 取模 ( 10^5 )，避免数值溢出，同时保留足够的低位数字（至少保留最后一位非零数字的前几位，防止中间计算丢失信息）。
3. 结果输出：右对齐输出 ( N )，并取 result % 10 作为最后一个非零数字。

五、关键点说明

• 模运算的选择：选择 ( 10^5 ) 作为模数是经验性选择，确保在 ( N \leq 10000 ) 时，去除零后的有效数字不会超过 5 位，从而避免因模数过小导致的信息丢失。
• 效率分析：时间复杂度为 ( O(N) )，对于 ( N \leq 10000 ) 完全可行，无需进一步优化。

该方法通过动态去除末尾零和合理使用模运算，高效地计算出阶乘的最后一个非零数字，避免了大数运算的复杂性。