阶乘以 n 个零结尾的数字
一个数的阶乘是所有不超过给定数的正整数的乘积。例如，5 的阶乘表示为 5!，等于所有不超过 5 的正整数的乘积:
5! = 5 x 4 x 3 x 2 x 1 = 120
一个数的阶乘十进制表示末尾的零的数量称为阶乘中的"尾随零"。例如，5 的阶乘是 120，尾随一个零;而 10 的阶乘是 3,628,800，尾随两个零。
问题描述
给定一个整数 n，我们必须确定阶乘有 n 个尾随零的正整数的数量。
示例
输入
n = 1
输出
5 6 7 8 9
解释
5! = 120
6!= 720
7! = 5040
8! = 40320
9! = 362880
可以看出，所有输出数字的阶乘都有 n 个尾随零，即 1 个尾随零。
输入
n = 2
输出
10 11 12 13 14
解释
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
可以观察到，所有输出数字的阶乘都有 n 个尾随零，即两个尾随零。
输入
n = 5
输出
No Output
解释
25! = 15511210043330985984000000 有 6 个尾随零。
一个数的阶乘恰好有 5 个尾随零，那么在其质因数分解中会有 5 个 5 的因数，但不会再有其他 5 的因数。然而，在质因数分解中拥有 5 个 5 的因数的最小数是 25!，它的阶乘中有 6 个零。
朴素求解方法
我们简单地迭代一系列整数(1 到 10^6)。对于每个数，我们检查其阶乘中零的数量是否等于给定数 n。如果是，则将其添加到 ans 向量中。如果阶乘中零的数量超过给定数 n，则跳出循环。
此方法不适用于较大的数字，因为会发生溢出。
算法
Function factorial(n):
Initialize fact = 1 for i = 2 to n: fact = fact * i return fact
Function count_trailing_zeros(num):
Initialize count = 0
while num % 10 = 0:
count = count + 1
num = num / 10
return count
Function find_numbers_with_n_trailing_zeros(n):
Initialize ans = empty vector
for i = 1 to 1e6:
a = count_trailing_zeros(factorial(i))
if a = n:
ans.push_back(i)
else if a > n:
break
if size of ans = 0:
print "No Output"
else:
for x in ans:
print x
时间和空间复杂度分析
时间复杂度:O(n*log n)
此代码的时间复杂度为 O(n*log n)，因为 factorial() 函数的时间复杂度为 O(n)，并且在 for 循环中针对 n 个值调用该函数，因此总时间复杂度为 O(n^2)。但是，如果尾随零的数量超过输入值 n，则循环会提前中断，从而显著减少迭代次数。
空间复杂度:O(n)
空间复杂度为 O(n)，因为程序使用向量存储结果。
优化方法
该技术查找阶乘中尾随零数量为指定值的所有数字。我们使用二分搜索策略来找出第一个尾随零数量为指定值的数字，然后遍历所有尾随零数量相同的后续数字，直到找到一个不包含"n"个尾随零的数字。
该方法包含以下步骤:
定义一个函数 count_trailing_zeros()，该函数接受一个整数 num 作为输入，并返回 num 的阶乘中尾随零的数量。
定义一个函数 find_numbers_with_n_trailing_zeros()，该函数接受一个整数 n 作为输入，并返回一个包含阶乘中尾随零为 n 个的整数向量。
使用二分搜索找到第一个尾随零为 n 的数字。
将所有尾随零为 n 的数字推送到答案。
返回答案。
算法
用于计算给定阶乘数 (num) 尾随零的函数:
count = 0
while num > 0:
num = num / 5
count += num
return count
查找具有 n 个尾随零的数字的函数(n):
start = 0
end = maximum integer value
while start < end:
mid = (start + end) / 2
count = count_trailing_zeros(mid)
if count < n:
start = mid + 1
else:
end = mid
ans = empty vector
while count_trailing_zeros(start) == n:
ans.push_back(start)
start++
return ans
打印向量 (ans) 的函数:
for i = 0 to ans.size(): print ans[i] + " "
主函数:
n = 3 result = find_numbers_with_n_trailing_zeros(n) print(result)
示例:C++ 程序
在下面的程序中，为了返回阶乘后有 n 个零的数字，我们使用了二分查找和素因数的概念。其思想是考虑阶乘 n 的素因数。素因数 2 和 5 总是会产生一个尾随零。很容易看出，素因数中 2 的数量总是大于或等于 5 的数量。因此，如果我们计算素因数中 5 的数量，就可以找出尾随零的数量。然后，我们使用二分查找来确定阶乘中尾随'n'个零的数字。
// C++ 程序，用于查找阶乘中尾随'n'个零的数字
#include <bits/stdc++.h>
using namespace std;
// 函数，用于计算给定阶乘数字的尾随零
int count_trailing_zeros(int num){
int count = 0;
while (num > 0){
num /= 5;
count += num;
}
return count;
}
// 函数用于查找尾随有 n 个零的数字
vector<int> find_numbers_with_n_trailing_zeros(int n){
int start = 0;
int end = INT_MAX;
// 二分查找第一个带有 n 个尾随零的数字
while (start < end){
int mid = (start + end) / 2;
int count = count_trailing_zeros(mid);
if (count < n)
start = mid + 1;
else
end = mid;
}
//将低位之后的所有数字推送至带有 n 个尾随零的位置。
vector<int> ans;
while (count_trailing_zeros(start) == n){
ans.push_back(start);
start++;
}
return ans;
}
void print(vector<int> &ans){
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
}
// 驱动函数
int main(){
int n = 3;
vector<int> result = find_numbers_with_n_trailing_zeros(n);
print(result);
return 0;
}
输出
15 16 17 18 19
时间和空间复杂度分析
时间复杂度:O(n)
代码的时间复杂度为 O(log n)，因为它使用二分查找来查找第一个尾随 n 个零的数字，这使得每次迭代时搜索空间减少一半。
空间复杂度:O(m)
空间复杂度为 O(m)，其中 m 表示尾随 n 个零的数字数量，因为程序将所有这些数字存储在一个向量中。
结论
本文讨论了两种查找阶乘以 n 个零结尾的数字的方法。为了加深理解，本文详细解释了方法的概念、示例、所用算法、C++ 程序解决方案以及时间和空间复杂度分析。
