题目描述：

LeetCode 793. Preimage Size of Factorial Zeroes Function

Let f(x) be the number of zeroes at the end of x!. (Recall that x! = 1 * 2 * 3 * ... * x, and by convention, 0! = 1.)

For example, f(3) = 0 because 3! = 6 has no zeroes at the end, while f(11) = 2 because 11! = 39916800 has 2 zeroes at the end. Given K, find how many non-negative integers x have the property that f(x) = K.

Example 1:
Input: K = 0
Output: 5
Explanation: 0!, 1!, 2!, 3!, and 4! end with K = 0 zeroes.

Example 2:
Input: K = 5
Output: 0
Explanation: There is no x such that x! ends in K = 5 zeroes.

Note:

• K will be an integer in the range [0, 10^9].

题目大意：

求阶乘得数末尾连续0的个数为K的所有整数的个数。

解题思路：

n!后缀0的个数K，等于不大于n的所有乘数中，因子5的个数。

计算公式为：K = (n / 5) + (n / 25) + (n / 125) + ... + n / (5^k)

由等比数列前N项和公式得不等式：K <= n / 4

n从4 * K开始递增枚举 + 验证即可

Python代码：

class Solution(object):
    def preimageSizeFZF(self, K):
        """
        :type K: int
        :rtype: int
        """
        n = 4 * K
        t = 0
        while t <= K:
            t = self.trailingZeroes(n)
            n += 1
            if t == K: return 5
        return 0

    def trailingZeroes(self, n):
        x = 5
        ans = 0
        while n >= x:
            ans += n / x
            x *= 5
        return ans

 

本文链接：http://bookshadow.com/weblog/2018/03/04/leetcode-preimage-size-of-factorial-zeroes-function/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码