问题分析

对于较小的 n（如 n ≤ 20），我们可以直接计算出 n! 的值并从后往前找第一个非零数字：

long long factorial(long long n) {
    long long ans = 1;
    for (int i = 1; i <= n; ++i) {
        ans *= i;
    }
    return ans;
}

但当 n 达到 10^7 时，n! 的值极其巨大（数百万位），即使使用 long double 或long long也无法保存，因此直接计算不可行。

思路

我们只需要找到阶乘末尾的第一个非零数字，而非整个阶乘。

核心思想：

  • 模拟乘法过程；
  • 每次乘完后去掉末尾的零；
  • 保留最后几位数字（如 1e9）即可。

实现思路

  1. 初始化 res = 1；

  2. 遍历 i = 1..n：

    • res *= i；
    • 去掉所有末尾的 0；
    • 取模 res %= 1000000000（保留最后 9 位，防止溢出）；

  3. 最终 res % 10 即为末尾第一个非零数字。

代码实现


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

typedef long long ll;

ll lastNonZeroDigit_factorial(ll n) {
    ll ans = 1;
    for (int i = 2; i <= n; ++i) {
        ans *= i;
        while (ans % 10 == 0)ans /= 10;
        ans %= int(1e9);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    ll n;
    cin >> n;
    cout << lastNonZeroDigit_factorial(n) % 10 << '\n';

    return 0;
}

关键点总结

  1. 避免大数计算：通过不断取模与去除 0 来防止溢出；