题目描述 N!后面有多少个连续的 0? N!的意思是阶乘,即从1一直乘到N的积。 输入 第一行, 1 个整数 N,表示数字个数,范围在[3…10000000000]。 输出 一个整数。 样例输入 复印件 5 样例输出 复印件 1
时间: 2024-09-25 14:03:15 浏览: 44
这个题目要求你计算给定自然数 \( N \) 的阶乘(\( N! \))尾部连续零的数量。为了得到连续的零,关键在于找出因数2和5在阶乘中的贡献,因为10=2*5。每一对2和5相乘都会贡献一个10,也就是一个0。但要注意,多余的5不会增加额外的0,因为每个2都已经提供了至少一个5(2*5=10)。
具体步骤如下:
1. 计算2在阶乘中出现的次数,因为每有一个2就会对应至少半个5(2和它的倍数会产生5),所以用 \( N \div 2 + (N \mod 2) \),其中\( \mod \)操作是取余。
2. 计算5在阶乘中出现的次数,因为5只提供了一个5(没有2参与的情况下),直接用 \( N \div 5 \)。
3. 最后,由于5的数量可能比2少,需要加上之前被2重复计算的5的数量,即用 \( N \div 25 \) 加上 \( N \mod 25 \) 向前累加的5数量。
需要注意的是,如果\( N \)不是5的倍数,\( N \mod 25 \) 不会有贡献。
现在给你一个示例代码:
```cpp
#include <iostream>
int countTrailingZeros(int n) {
int count2 = n / 2; // 从2的幂开始计数
int count5 = n / 5;
// 需要加上那些被2的幂覆盖掉的5
for (int i = 10; i <= n; i *= 25) {
count2 += i / 2;
count5 += i / 5;
}
return std::min(count2, count5); // 取两者中的较小值,因为多余的5不会增加0
}
int main() {
int N;
std::cin >> N;
int result = countTrailingZeros(N);
std::cout << result << "\n";
return 0;
}
```
阅读全文