参考资料

题目描述

给定一个整数 n（1 ≤ n ≤ 10^7），要求输出 n!（n 的阶乘）中末尾第一个非零数字。

题目链接

问题分析

对于较小的 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` 或大整数也无法保存，因此**直接计算不可行**。

---

## 思路

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

分析阶乘中的末尾零产生的原因：

* 每一对 `(2,5)` 会产生一个零；
* 因此我们可以统计 5 的个数并与 2 配对去除掉它们的影响；
* 同时在计算过程中每次取模避免数字过大。

**核心思想：**

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

---

##  实现思路

1. 初始化 `res = 1`；
2. 遍历 `i = 1..n`：

   * `res *= i`；
   * 去掉所有末尾的 0；
   * 取模 `res %= 1000000000`（保留最后 9 位，防止溢出）；
3. 最终 `res % 10` 即为末尾第一个非零数字。

---

##  代码实现

```cpp

#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); // 1e9是double需要强制转换
    }
    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 来防止溢出；

  2. 2 与 5 的抵消原理：每对 (2,5) 会产生一个 0，去掉它们即可；

  3. 优化输出：

    ios::sync_with_stdio(false);
cin.tie(0);

    关闭流同步，提高输入输出效率。

思考延伸

  • 该方法不仅适用于阶乘问题，还可以推广到“组合数末尾非零数字”类问题；
  • 若需要更多尾部非零数字（例如末尾 5 位非零数），可调整取模范围（如 1e12）。

总结一句话：

“通过逐步消去 2 和 5 的影响，并限制保留位数，我们无需计算完整阶乘即可求出末尾非零数字。”