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，找出多少个非负整数 x ，能满足 f(x) = K 。

示例 1：
输入：K = 0
输出：5
解释：0!, 1!, 2!, 3!, and 4! 均符合 K = 0 的条件。

示例 2：
输入：K = 5
输出：0
解释：没有匹配到这样的 x!，符合 K = 5 的条件。

提示：
K 是范围在 [0, 109] 的整数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/preimage-size-of-factorial-zeroes-function

2.思路

（1）二分搜索
① 在做此题之前，需要先了解172.阶乘后的零这题，该思路的解法需要复用其函数trailingZeroes(int n)，其返回值为 n! 结果中尾随零的数量。
② 对于本题，通过分析可得，找出有多少个 n 满足trailingZeroes(int n)==k，就等价于先找出满足条件的 n 的最小值和最大值，然后两者相减再加一，这样就可以算出来满足条件的 n 的个数了。
③ 又由于n是递增的，故n!也是递增的，即n!是有序的，所以求解上述的最大值和最小值就相当于二分搜索中的搜索左边界和搜索右边界。

3.代码实现（Java）

//思路1————二分搜索
public int preimageSizeFZF(int k) {
    return (int)(right_bound(k)-left_bound(k)+1);
}

//求解 n! 结果中尾随零的数量
public long trailingZeroes(long n){
    long res = 0;
    long factor = 5;
    while(factor<=n){
        res+=n/factor;
        factor*=5;
    }
    return res;
}

//搜索trailingZeroes(n) == K 的左侧边界
public long left_bound(int target){
    long left = 0;
    long right = Long.MAX_VALUE;
    while(left<right){
        long mid = left+(right-left)/2;
        if(trailingZeroes(mid)<target){
            left=mid+1;
        }else if(trailingZeroes(mid)>target){
            right=mid;
        }else{
            right=mid;
        }
    }
    return left;
}

//搜索trailingZeroes(n) == K 的右侧边界
public long right_bound(int target){
    long left = 0;
    long right = Long.MAX_VALUE;
    while(left<right){
        long mid = left+(right-left)/2;
        if(trailingZeroes(mid)<target){
            left=mid+1;
        }else if(trailingZeroes(mid)>target){
            right=mid;
        }else{
            left=mid+1;
        }
    }
    return left-1;
}