难度: Hard
f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 * 2 * 3 * ... * x，且 0! = 1 。
f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。给定 k，找出返回能满足 f(x) = k 的非负整数 x 的数量。
示例 1：
输入：k = 0 输出：5 解释：0!, 1!, 2!, 3!, 和 4! 均符合 k = 0 的条件。
示例 2：
输入：k = 5 输出：0 解释：没有匹配到这样的 x!，符合 k = 5 的条件。
示例 3:
输入: k = 3 输出: 5
提示:
0 <= k <= 109运行时间: 24 ms
内存: 16.1 MB
class Solution:
def preimageSizeFZF(self, k: int) -> int:
left = 4*k
right = 5*(k+1)
while left <= right:
mid = left + (right-left)//2
temp = self.f(mid)
if temp >= k:
right = mid - 1
else:
left = mid + 1
lo = left
left = 4*k
right = 5*(k+1)
while left <= right:
mid = left + (right-left)//2
temp = self.f(mid)
if temp > k:
right = mid - 1
else:
left = mid + 1
hi = right
return int(hi-lo+1)
def f(self, n: int) -> int:
res = 0
while n:
n //= 5
res += n
return res
题解采用了二分查找的方法来确定具有k个末尾0的最小和最大的x值。首先，函数f(n)计算n的阶乘末尾0的数量，这是通过计算n可以被5的多少次幂整除来实现的。对于给定的k，通过使用两次二分查找，一次寻找满足f(x) = k的最小x值，另一次寻找最大x值。如果k不可能达到（如中间出现跳跃），这两个查找返回的区间会是空的，否则区间内每一个整数都满足条件。搜索范围设定在4k到5(k+1)之间是基于阶乘末尾0的数量增长的大致速度推导出的。
时间复杂度: O(log^2(n))
空间复杂度: O(1)
class Solution:
def preimageSizeFZF(self, k: int) -> int:
# 设置二分查找的初始左右界限
left = 4 * k
right = 5 * (k + 1)
# 第一次二分查找，找到f(x) >= k的最小x
while left <= right:
mid = left + (right - left) // 2
temp = self.f(mid)
if temp >= k:
right = mid - 1
else:
left = mid + 1
lo = left
# 重新设置左右界限
left = 4 * k
right = 5 * (k + 1)
# 第二次二分查找，找到f(x) <= k的最大x
while left <= right:
mid = left + (right - left) // 2
temp = self.f(mid)
if temp > k:
right = mid - 1
else:
left = mid + 1
hi = right
# 计算满足条件的x的数量
return int(hi - lo + 1)
def f(self, n: int) -> int:
# 计算n的阶乘的末尾0的数量
res = 0
while n:
n //= 5
res += n
return res
选择这个范围是基于阶乘末尾0的数量增长规律。因为每个末尾的0是由因子5和因子2组成的，而在任何给定的数字序列中，因子2的数量总是多于因子5的数量。因此，末尾0的数量主要由因子5的数量决定。一个粗略的估算表明，n的阶乘大约每隔5个数就增加一个额外的末尾0。因此，大约每增加5个新的末尾0，n需要增加大约5的倍数。所以从4k到5(k+1)的范围是一个保守的估计，确保能够涵盖从k个0增加到k+1个0的所有可能的n值。
第一次二分查找的目的是找到满足f(x) >= k的最小的x值，这意味着找到第一个阶乘尾部有至少k个零的数。这是为了确定满足条件的下界。而第二次二分查找的目的是找到满足f(x) <= k的最大的x值，即找到阶乘尾部零的数量恰好是k的最大数，这是为了确定满足条件的上界。这样通过两次查找，我们可以确定所有满足阶乘尾部有k个零的数的范围。
在计算阶乘尾部的0的数量时，每个0都来源于因子10，而10可以分解为2和5。在任何给定的n中，产生2的因子的数字（如2、4、6等）比产生5的因子的数字（如5、10、15等）要多，因此2的因子在阶乘中总是充足的。这意味着末尾0的数量完全由因子5的数量决定，因此在计算时只需要关注n能被5的多少次幂整除。