C++ 末尾有n个零的阶乘数

一个数的阶乘是从1到给定数之间所有正整数的乘积。例如，5的阶乘表示为5！，等于1到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个末尾的零，即一个末尾的零。

输入

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的因子的最小数是25!，它的阶乘中有6个零。

朴素解法

我们简单地迭代一个整数范围（从1到106）。对于每个数，我们检查其阶乘中零的数量是否等于给定的数n。如果是这样，我们将其添加到ans向量中。如果阶乘中的末尾零的数量超过了给定的数n，我们中断循环。

对于较大的数，此方法不适用，因为会发生溢出。

算法

函数阶乘(n):

Initialize fact = 1
for i = 2 to n:
   fact = fact * i
return fact

计算尾部的零的函数count_trailing_zeros（num）：

Initialize count = 0
while num % 10 = 0:
    count = count + 1
    num = num / 10
return count

功能 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个尾随零的起始数字推入ans。
返回ans。

算法

计算给定阶乘数(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

打印向量（答案）的函数：

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++ program to find numbers which have ‘n’ trailing zeros in their factorial
#include <bits/stdc++.h>
using namespace std;
// function to count trailing zeros of the given factorial number
int count_trailing_zeros(int num){
    int count = 0;
    while (num > 0){
        num /= 5;
        count += num;
    }
    return count;
}
// function to find the number which have n trailing zeros
vector<int> find_numbers_with_n_trailing_zeros(int n){
    int start = 0;
    int end = INT_MAX;
    // binary search for first number with n trailing zeros
    while (start < end){
        int mid = (start + end) / 2;
        int count = count_trailing_zeros(mid);
        if (count < n)
            start = mid + 1;
        else
            end = mid;
    }
    // push all numbers after low with n trailing zeros.
    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] << " ";
}
// driver function
int main(){
    int n = 3;
    vector<int> result = find_numbers_with_n_trailing_zeros(n);
    print(result);
    return 0;
}