题目名称

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 的数量。

示例

输入：k = 0
输出：5
解释：0!, 1!, 2!, 3!, 和 4! 均符合 k = 0 的条件。

题解

在这里借用大佬的思路

如何求x的阶乘末尾0的个数?
10进制中只有2和5相乘才会得到10，也就是每有一对2和5，就多一个末尾的0
而阶乘又是从1开始乘到x，所以2的个数总是比5多，那么问题转化为求x！中有多少个5作为因子
公式为 k = x/5 + x/5^2 + x/5^3 + ……
如何求x?
根据上面的公式，x/5 + x/5^2 + x/5^3 + …… = k
=> x/5 < k <=10^9
=> x < 5 10^9 容易想到在[0, 5k]内二分求解x
符合的x个数有多少个?
显然，x每+5，阶乘就会至少多乘一个5，末尾就会至少多一个0，所以如果上面的x有解，那就是5个，如果无解就是0

在获取x 包含有多少个5的时候，需要我们使用递归的方式，类似于 25,125 这种和 5 的n次方相关其实并不单纯是只包含有一个

像 25 除以 5 后得到的商为 5，这样就代表着 25, 并不单纯的只包含 5 个 5，而是 6 个 5

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * @param {number} k
 * @return {number}
 */
 var preimageSizeFZF = function(k) {
    if(k === 0) return 5
    let x = 5 * k
    let half = x >> 1, left = 0, right = x
    while(half < right && half > left) {
        let num = get5(half)
        if(num < k) {
            left = half
            half = Math.ceil((half + right) / 2)
        } else if(num === k) {
            return 5
        } else {
            right = half
            half = Math.ceil((half + left) / 2)
        }
    }
    if(half === left || half === right) {
        if(get5(half) === k) return 5
    }
    return 0
};

const get5 = (x) => {
    let num = Math.floor(x / 5)
    while(x) {
        x = Math.floor(x / 5)
        num += Math.floor(x / 5)
    }
    return num
}