共计 1781 个字符，预计需要花费 5 分钟才能阅读完成。
题目形容
这是 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 末端有 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 <= 10^9$
数学 + 二分
对于一个 $n! = 1 \times 2 \times … \times (n – 1) \times n$ 而言，其最终后果尾部蕴含 $0$ 的数量取决于其被累乘 $10$ 的次数，而 $10$ 可通过质因数 $2$ 和 $5$ 相乘而来，因而假如对 $n!$ 进行阶乘合成，最终合成出 $2^p$ 和 $5^q$ 的话，那么最终后果尾部蕴含 $0$ 的个数为 $q$ 个（可证实 $p >= q$ 始终满足）。
因而原问题转化为：在非负整数中，有多少个数进行阶乘合成后，所含质因数 $5$ 的个数恰好为 $k$ 个。
同时咱们可知：随着 $n$ 的增大，其所能合成进去的 $5$ 的个数必然是递增的。
基于此，咱们能够通过「二分 + 容斥原理」来得出合成 $5$ 个数恰好为 $k$ 的间断段长度。假如咱们存在函数 f(k) 可失去非负整数中合成 $5$ 个数为小于等于 k 的个数，那么最终 f(k) - f(k - 1) 即是答案。
在枯燥函数上求解小于等于 k 宰割点，可通过「二分」来做。剩下的问题是，如何求得给定 x 时，其阶乘合成所蕴含 $5$ 个个数，这能够通过 $O(\log{x})$ 的筛法来做。
最初还要确定二分的值域，因为咱们是求阶乘合成中 $5$ 的个数，因而值域的上界为 $5k$，利用 $k$ 的范畴为 $1e9$，间接取成 $1e10$ 即可。
Java 代码：
class Solution {public int preimageSizeFZF(int k) {if (k <= 1) return 5;
return f(k) - f(k - 1);
}
int f(int x) {long l = 0, r = (long) 1e10;
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 <= 1) return 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
}- 工夫复杂度：$O(\log^2{k})$
- 空间复杂度：$O(1)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.793 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
