题解 | #阶乘末尾非零数字#
阶乘末尾非零数字
https://www.nowcoder.com/practice/248c8fbee56e491aa147b67b9c082da0
题目链接
题目描述
给定一个正整数 n，请求出 n! (n的阶乘) 的十进制表示中，从右往左数第一个非零的数字。
解题思路
这个问题的核心挑战在于 n! 的值会非常快地增长，对于稍大的 n（例如 n=20），其阶乘结果就会超出标准64位整型（long long）的存储范围。因此，直接计算出 n! 的完整值再提取末位数字是不可行的。
我们需要一种在计算过程中就能控制数值大小的方法。思路如下：
-
迭代计算：我们可以模拟阶乘的计算过程，从 1 乘到
n。维护一个变量res，用于存储我们关心的“末尾部分”的乘积。 -
移除尾随零：阶乘结果中的尾随零是由因子 2 和 5 相乘（
2 * 5 = 10）产生的。我们只关心第一个非零数字，所以每当乘积res的末尾出现 0，就应该立即移除它。这可以通过一个循环实现：只要res % 10 == 0，就执行res /= 10。 -
防止溢出：即使移除了尾随的零，
res的值在乘以i时仍然可能增长得非常快，最终导致溢出。为了解决这个问题，我们可以在每次移除尾零后，对res进行取模操作，只保留其末尾的几位数字。例如res %= 1000000000。- 为什么这是可行的？因为我们最终只关心结果的个位数字 (
res % 10)。保留末尾的几位（如9位）作为“缓冲区”，足以确保在下一次乘以i（i不会太大）并移除尾零后，得到的个位数字是正确的。这个缓冲区保证了我们不会因为过早地取模而丢失影响最终结果个位数的关键信息。
- 为什么这是可行的？因为我们最终只关心结果的个位数字 (
-
特殊情况：根据数学定义，
0! = 1，所以当输入为 0 时，应输出 1。
综上所述，我们的算法是：
- 初始化
res = 1。 - 从
i = 1循环到n。 - 在循环中，
res *= i。 - 移除
res的所有尾随零。 - 对
res取一个较大的模（如 100000）以防止溢出。 - 循环结束后，
res % 10就是最终答案。
代码
#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long n;
cin >> n;
if (n == 0) {
cout << 1 << endl;
return 0;
}
long long res = 1;
for (long long i = 1; i <= n; ++i) {
res *= i;
while (res % 10 == 0) {
res /= 10;
}
res %= 1000000000; // 保留足够的末位以防止溢出和保证精度
}
cout << res % 10 << endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
if (n == 0) {
System.out.println(1);
return;
}
long res = 1;
for (long i = 1; i <= n; i++) {
res *= i;
while (res % 10 == 0) {
res /= 10;
}
res %= 1000000000; // 保留缓冲区
}
System.out.println(res % 10);
}
}
n = int(input())
if n == 0:
print(1)
else:
res = 1
for i in range(1, n + 1):
res *= i
while res % 10 == 0:
res //= 10
# Python可以处理大整数，但我们仍然可以取模
# 以保持数字较小，从而可能加快计算速度。
res %= 1000000000
print(res % 10)
算法及复杂度
- 算法：模拟、数学
- 时间复杂度：
。我们有一个主循环，从 1 迭代到
n。在循环内部，while循环用于移除尾随零，其执行次数取决于res和i中包含的因子 5 和 2 的数量，这个次数相对较小。因此，时间复杂度近似为。
- 空间复杂度：
。我们只需要常数级别的额外空间。
