1.题目基本信息

1.1.题目描述

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.2.题目地址

https://leetcode.cn/problems/preimage-size-of-factorial-zeroes-function/description/

2.解题方法

2.1.解题思路

二分查找。

记theta(x)=sum(floor(x/(5j)) for j in range(1,inf))为x!后0的个数；theta(x)单调不减，找到最小的一个x_k，使theta(x_k)>=k，那么x_(k+1)-x_k即为题解；由等比数列求和公式可知theta(x)>=floor(x/5)，则theta(5x)>=x，则可以确定k规模下的x二分的右边界为5k

2.2.解题步骤

第一步，预处理。构建theta函数计算x!数乘后面0的个数

第二步，二分。x_k在[0,5*k]之间，找到最小的一个x_k使得theta(x_k)>=k

3.解题代码

python代码

class Solution:
    def preimageSizeFZF(self, k: int) -> int:
        # 思路：二分查找。记theta(x)=sum(floor(x/(5**j)) for j in range(1,inf))为x!后0的个数；theta(x)单调不减，找到最小的一个x_k，使theta(x_k)>=k，那么x_(k+1)-x_k即为题解；由等比数列求和公式可知theta(x)>=floor(x/5)，则theta(5*x)>=x，则可以确定k规模下的x二分的右边界为5*k
        # 参考：Leetcode 172. 阶乘后的零
        # 第一步，预处理。构建theta函数计算x!数乘后面0的个数
        def theta(x):
            ans = 0
            while x:
                ans += x // 5
                x //= 5
            return ans
        # 第二步，二分。x_k在[0,5*k]之间，找到最小的一个x_k使得theta(x_k)>=k
        def helper(k:int) -> int:
            left, right = 0, 5 * k
            while left <= right:
                mid = (right - left) // 2 + left
                if theta(mid) >= k:
                    right = mid - 1
                else:
                    left = mid + 1
            return left
        return helper(k + 1) - helper(k)

4.执行结果