铜梁网站建设合肥seo推广排名

原文地址：Smallest number with at least n trailing zeroes in factorial

已知一个数字n，找出一个数的阶乘，这个阶乘的尾部至少含有n个0。

例如：

输入: n = 1
输出: 5 
1!, 2!, 3!, 4! 尾部不包含0。
5! = 120, 尾部包含一个0。输入: n = 6
输出: 26
26! = 403291461126605635584000000.

在文中《计算一个数的阶乘的尾部的0的个数》一文中，我们已经讨论0的个数等于$x!$中5的素数的个数。在下面的式子就是计算5的个数：

Trailing 0s in x! = Count of 5s in prime factors of x!= floor(x/5) + floor(x/25) + floor(x/125) + ....

下面看几个例子来观察模式：

5!尾部有一个0 
[从6到9的尾部的所有数字都是一个0]10!尾部有两个0
[从11到14的尾部的所有数字都是一个0]15!到19!尾部有3个020!到24!尾部有4个025!到29!尾部有6个0

我们注意到，最大数值的阶乘包含尾部的0的个数是$5*n$。

所以为了找到阶乘尾部包含0的最小值，利用$0$到$5*n$范围的二分查询。然后再找到阶乘尾部包含n个0的最小值。

// C++ program tofind smallest number whose
// factorial contains at least n trailing
// zeroes.
#include<bits/stdc++.h>
using namespace std;// Return true if number's factorial contains
// at least n trailing zero else false.
bool check(int p, int n)
{int temp = p, count = 0, f = 5;while (f < temp){count += temp/f;f = f*5;}return (count >= n);
}// Return smallest number whose factorial
// contains at least n trailing zeroes
int findNum(int n)
{// If n equal to 1, return 5.// since 5! = 120.if (n==1)return 5;// Initalising low and high for binary// search.int low = 0;int high = 5*n;// Binary Search.while (low <high){int mid = (low + high) >> 1;// Checking if mid's factorial contains// n trailing zeroes.if (check(mid, n))high = mid;elselow = mid+1;}return low;
}// driver code
int main()
{int n = 6;cout << findNum(n) << endl;return 0;
}

输出：

26