题目解析
题目描述
给定一个正整数 m,请你统计一共有多少个正整数 n 满足,n 的阶乘的末尾连续 0 的数量恰好为 m。输出满足条件的 n 的数量以及所有满足条件的 n。
思路分析
我们可以发现,阶乘末尾的 0 是由 2 和 5 相乘产生的。在阶乘中,因子 2 的数量总是大于因子 5 的数量,所以我们只需要关注因子 5 的数量即可。
首先我们需要一个函数 count_trailing_zeros 来计算 n! 中末尾连续 0 的个数。这个函数会不断地将 n 整除以 5,并累加结果,直到 n 小于 5。
接下来,我们需要找到所有满足条件的正整数 n。根据题意,n! 中末尾连续零的个数恰好等于 m,则有:
Copycount_trailing_zeros(n) == m
我们可以使用二分查找法在范围 [1, m * 5] 内查找符合条件的正整数 n。当找到一个符合条件的 n 时,向左和向右扩展该区间内满足条件的所有正整数,并将它们添加到结果列表中。
最后输出结果列表即可。
实现代码
#include <iostream>
#include <vector>
using namespace std;
int count_trailing_zeros(int n) {
int count = 0;
while (n >= 5) {
n /= 5;
count += n;
}
return count;
}
vector<int> find_numbers_with_m_trailing_zeros(int m) {
int low = 1, high = m * 5;
vector<int> results;
while (low <= high) {
int mid = (low + high) / 2;
int zeros = count_trailing_zeros(mid);
if (zeros == m) {
int left = mid - 1, right = mid + 1;
while (count_trailing_zeros(left) == m)
left--;
while (count_trailing_zeros(right) == m)
right++;
for (int i = left + 1; i < right; ++i)
results.push_back(i);
break;
} else if (zeros < m) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return results;
}
int main() {
int m;
cin >> m;
vector<int> numbers_with_m_trailing_zeros = find_numbers_with_m_trailing_zeros(m);
if (!numbers_with_m_trailing_zeros.empty()) {
cout << numbers_with_m_trailing_zeros.size() << endl;
for (int number : numbers_with_m_trailing_zeros)
cout << number << " ";
cout << endl;
} else {
cout << 0 << endl;
}
return 0;
}