题目
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:
Kwill be an integer in the range[0, 10^9].
题目大意
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，找出多少个非负整数x ，有 f(x) = K 的性质。
注意：
- K 是范围在 [0, 10^9] 的整数。
解题思路
- 给出一个数 K，要求有多少个 n 能使得 n！末尾 0 的个数等于 K。
- 这一题是基于第 172 题的逆过程加强版。第 172 题是给出
n，求得末尾 0 的个数。由第 172 题可以知道，n！末尾 0 的个数取决于因子 5 的个数。末尾可能有K个 0，那么n最多可以等于5 * K，在[0, 5* K]区间内二分搜索，判断mid末尾 0 的个数，如果能找到K，那么就范围 5，如果找不到这个K，返回 0 。为什么答案取值只有 0 和 5 呢？因为当n增加 5 以后，因子 5 的个数又加一了，末尾又可以多 1 个或者多个 0(如果加 5 以后，有多个 5 的因子，例如 25，125，就有可能末尾增加多个 0)。所以有效的K值对应的n的范围区间就是 5 。反过来，无效的K值对应的n是 0。K在5^n的分界线处会发生跳变，所有有些值取不到。例如，n在[0,5)内取值，K = 0；n在[5,10)内取值，K = 1；n在[10,15)内取值，K = 2；n在[15,20)内取值，K = 3；n在[20,25)内取值，K = 4；n在[25,30)内取值，K = 6，因为 25 提供了 2 个 5，也就提供了 2 个 0，所以K永远无法取值等于 5，即当K = 5时，找不到任何的n与之对应。 - 这一题也可以用数学的方法解题。见解法二。这个解法的灵感来自于：n！末尾 0 的个数等于 [1,n] 所有数的因子 5 的个数总和。其次此题的结果一定只有 0 和 5 (分析见上一种解法)。有了这两个结论以后，就可以用数学的方法推导了。首先 n 可以表示为 5 进制的形式
- 上面式子中，所有有因子 5 的个数为：
- 这个总数就即是 K。针对不同的 n，an 的通项公式不同，所以表示的 K 的系数也不同。cn 的通项公式呢？
- 由上面这个递推还能推出通项公式(不过这题不适用通项公式，是用递推公式更方便)：
- 判断 K 是否能表示成两个数列的表示形式，等价于判断 K 是否能转化为以 Cn 为基的变进制数。到此，转化成类似第 483 题了。代码实现不难，见解法二。 ��解法二。
参考代码
package leetcode// 解法一 二分搜索
func preimageSizeFZF(K int) int {low, high := 0, 5*Kfor low <= high {mid := low + (high-low)>>1k := trailingZeroes(mid)if k == K {return 5} else if k > K {high = mid - 1} else {low = mid + 1}}return 0
}func trailingZeroes(n int) int {if n/5 == 0 {return 0}return n/5 + trailingZeroes(n/5)
}// 解法二 数学方法
func preimageSizeFZF1(K int) int {base := 0for base < K {base = base*5 + 1}for K > 0 {base = (base - 1) / 5if K/base == 5 {return 0}K %= base}return 5
})
