宫水三叶的刷题日记

V1

2022/08/28阅读:13主题:前端之巅同款

793. 阶乘函数后 K 个零 : 经典「数学 + 二分」运用题

题目描述

这是 LeetCode 上的 793. 阶乘函数后 K 个零 ,难度为 困难

Tag : 「数学」、「二分」、「容斥原理」

f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 * 2 * 3 * ... * x,且 0! = 1

例如, f(3) = 0,因为 3! = 6 的末尾没有 0 ;而 f(11) = 2,因为 11!= 39916800 末端有 20

给定 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

提示:

数学 + 二分

对于一个 而言,其最终结果尾部包含 的数量取决于其被累乘 的次数,而 可通过质因数 相乘而来,因此假设对 进行阶乘分解,最终分解出 的话,那么最终结果尾部包含 的个数为 个(可证明 始终满足)。

因此原问题转化为:在非负整数中,有多少个数进行阶乘分解后,所含质因数 的个数恰好为 个。

同时我们可知:随着 的增大,其所能分解出来的 的个数必然是递增的。

基于此,我们可以通过「二分 + 容斥原理」来得出分解 个数恰好为 的连续段长度。假设我们存在函数 f(k) 可得到非负整数中分解 个数为小于等于 k 的个数,那么最终 f(k) - f(k - 1) 即是答案。

在单调函数上求解小于等于 k 分割点,可通过「二分」来做。剩下的问题是,如何求得给定 x 时,其阶乘分解所包含 个个数,这可以通过 的筛法来做。

最后还要确定二分的值域,由于我们是求阶乘分解中 的个数,因此值域的上界为 ,利用 的范围为 ,直接取成 即可。

Java 代码:

class Solution {
    public int preimageSizeFZF(int k) {
        if (k <= 1return 5;
        return f(k) - f(k - 1);
    }
    int f(int x) {
        long l = 0, r = (long1e10;
        while (l < r) {
            long mid = l + r + 1 >> 1;
            if (getCnt(mid) <= x) l = mid;
            else r = mid - 1;
        }
        return (int)r;
    }
    long getCnt(long x) {
        long ans = 0;
        while (x != 0) {
            ans += x / 5; x /= 5;
        }
        return ans;
    }
}

TypeScript 代码:

function preimageSizeFZF(k: number): number {
    if (k <= 1return 5
    return f(k) - f(k - 1)
};
function f(x: number): number {
    let l = 0n, r = BigInt("10000000000")
    while (l < r) {
        const mid = l + r + 1n >> 1n
        if (getCnt(mid) <= x) l = mid
        else r = mid - 1n
    }
    return Number(r)
}
function getCnt(x: bigint): bigint {
    let ans = 0n
    while (x != 0n) {
        ans += BigInt(Math.floor(Number(x / 5n))); x = BigInt(Math.floor(Number(x / 5n)))
    }
    return ans
}
  • 时间复杂度:
  • 空间复杂度:

最后

这是我们「刷穿 LeetCode」系列文章的第 No.793 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1