【leetcode】【2022/8/28】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 的数量。
• 示例一：
  • 输入：k = 0。
  • 输出：5。
  • 解释：0!, 1!, 2!, 3! 和 4! 均符合 k = 0 的条件。

核心思路：

• 该题核心在于数学推导，一开始看到题没有思路，看了几个题解（包括 leetcode 172 阶乘后的零的题解），总算是理解了该题是如何运用二分法找到答案的。
• 首先要理解 leetcode 172 阶乘后的零，如题目所示，172 题要求的是 x 的阶乘 x! 末尾有多少个零。
  • 由分析可得，末尾有多少个零相当于阶乘中有多少个质因子 5。【该部分的分析可看 172 题的官方题解】
• 而质因子 5 的个数在阶乘过程中是不断递增的，x 的阶乘中末尾 0 的数量为 f(x)，则必定有 f(x) <= f(y), x <= y。
  • 末尾 0 的个数为 0，则 x 可取 0、1、2、3 和 4；末尾 0 的个数为 1，则 x 可取 5、6、7、8 和 9。
  • 那么假设 help(k) 代表的是满足 x 的阶乘末尾 0 的数量等于或小于 k 的 x 的数目，则 help(1) = 10, help(0) = 5，因此能满足 f(x) = 0 的非负整数 x 的数量为 help(1) - help(0) = 5。
• 因此能满足 f(x) = k 的非负整数 x 的数量为 help(k+1) - help(k)。
• 关键在于如何求 help(k)。
  • 如果理解了题意，应该比较容易考虑到二分搜索，二分搜索找到最后一个满足 f(x) <= k 的位置，就相当于是求出了 help(k)。
  • 而二分的边界为 [0, 5*k]，之所以是 5*k，可以很直观的看出来 5*k 比 k 多一个质因子 5。
• 到此需要注意的点应该都已介绍完毕，数学推导的相关题目一直是我弱项，更严谨的解释可以看官方题解，我这里只是简单写一写思路脉络。

代码实现：

class Solution
{
private:
    using ll = long long;
    ll help(int k)
    {
        ll l = 0;
        ll r = 5LL * k; // 上界
        // 找到最后一个满足 zeta(mid) <= k 的位置 mid
        while(l <= r)
        {
            ll mid = l + (r - l) / 2;
            if(zeta(mid) < k)
                l = mid + 1;
            else r = mid - 1;
        }
        return l+1;
    }
    int zeta(ll n) // 求 n! 中末尾零的个数，zeta 函数即题目中所说的 f 函数
    {
        int ans = 0;
        while(n > 0)
        {
            n /= 5;
            ans += n;
        }
        return ans;
    }
public:
    int preimageSizeFZF(int k)
    {
        // k = 0, x = 0, 1, 2, 3, 4;
        // k = 1, x = 5, 6, 7, 8, 9;
        if(k <= 1) return 5;
        return help(k+1) - help(k);
    }
};
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
35
36
37

参考内容：

• leetcode 172 官方题解
• leetcode 793 官方题解