C练题笔记之：Leetcode-793. 阶乘函数后 K 个零

题目：

 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：

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

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

输入: k = 3
输出: 5
 

提示:

0 <= k <= 109

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/preimage-size-of-factorial-zeroes-function
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

结果：

解题思路：

我一开始想要把乘积算出来，然后很快就发现天真了。。。

于是取看了题解，感谢题解中【爪哇缪斯】图解LeetCode 这篇图解，根据他的题解就真的能够明白为什么。——>大佬题解

简单说下题解中的思路：

首先我们要确定的是，乘积是否多一个0出来，取决于5 和 2 组合的个数，（至于为什么。。。我不知道，反正看看规律就是这样）。因为2出现的次数太多，不利于计算，这里用5计算。因此我们乘积中出现多少个0，完全取决于5的个数。

由此可以看出我们出现的5的个数就是0的个数。 

然后5*5， 5*5 * 5这种5的次方的值，因为其本身的值会被5整除，这样可能会误导我们个数的计算，因此这部分需要单独拿出来算1个5.。

 因此这题计算的k 如果存在一个 nums / 5 + nums / 25 + nums / 625 。。。的和，那就存在有k个0存在的场景。

最后，既然是一致计算5的个数，那就很容易明白，我们每5个数会多出至少1个0，所以我们返回的个数只可能是0 和 5.

最后注意：虽然不计算乘积，但是因为要和5做计算，会超出int范围！

代码：

// 由题解可以学习到，其实这道题就是求相乘的数字中出现5和5的倍数的个数
// 因此我们从start到end之间只需要保证5和5的倍数存在的个数和等于k存在那就存在5个。
int preimageSizeFZF(int k){
    long long start = 0;
    long long end = (long long)5 * k;
    while(start <= end) {
        long long sum = 0;
        long long num = 5;
        long long mid = (end - start)/2 + start;
        while (num <= mid) {
            sum += (mid / num); // 当前mid包含5的个数，5的倍数的个数的和。
            num *= 5;
        }
        if (sum == k) {
            // 说明5和5的倍数的个数之和为k，也就是可以存在有k个0存在的场景。
            return 5;
        } else if (sum < k) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return 0;
}