793. 阶乘函数后 K 个零

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

数据范围：

$0\le k \le 10^9$

题解：

参考 172. 阶乘后的零 | Luobuyu’s Blog。可以快速计算出来 $x!$ 的尾零个数，并且是单调不减的。因为 $5$ 的倍数越来越多。求恰好有 $k$ 个尾零的 $x$ 的个数，可以先求出来至少有 $k + 1$ 个零的最小的 $x_1$ ，然后求出来至少有 $k$ 个零的最小的 $x_2$ 。最后二者作差可以得到答案。

求至少有 $k$ 个尾零的 $x$ 。可以使用二分查找，每次调用上一题的算法，快速求出来尾零的个数做判断。

代码：

auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int cntx0(long long x)
    {
        // 计算 x! 末尾 0 的个数
        int cnt = 0;
        while (x)
        {
            x /= 5;
            cnt += x;
        }
        return cnt;
    }
    int solve(int k)
    {
        // k 个0需要找 k 个 5 的 x。
        long long l = 5, r = 5ll * k;
        long long ans = 0;
        while (l <= r)
        {
            long long mid = l + ((r - l) >> 1);
            if (cntx0(mid) >= k)
            {
                ans = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        return ans;
    }
    int preimageSizeFZF(int k)
    {
        // 末尾至少有 k + 1个0的减去 末尾至少有 k 个 0的
        // solve(k + 1) - solve(k);
        return solve(k + 1) - solve(k);
    }
};