LeetCode-Go 题解精讲793. Preimage Size of Factorial Zeroes Function阶乘末尾零的原像个数【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 793 题「Preimage Size of Factorial Zeroes Function」展开讲解如何用 Go 求出满足f(x) K的非负整数x的个数其中f(x)是x!末尾零的个数。这道题是 172 题「Factorial Trailing Zeroes」的逆向加强版也是 483 题「Smallest Good Base」在数学上的同构问题。读完本文你将掌握两条可复现的求解路线基于二分搜索的通用解法解法一以及基于 5 进制展开与变进制数判定的数学解法解法二并看到它们在 LeetCode-Go 仓库中的完整 Go 实现与单元测试。题目描述设f(x)为x!末尾零的个数约定0! 1。例如f(3) 0因为3! 6末尾没有 0f(11) 2因为11! 39916800末尾有 2 个 0。给定整数K求有多少个非负整数x满足f(x) K。示例 1输入K 0 输出5 解释0!、1!、2!、3!、4! 的末尾都恰好有 0 个零。示例 2输入K 5 输出0 解释不存在任何 x 使得 x! 的末尾恰好有 5 个零。注意K是范围在[0, 10^9]内的整数。题目大意f(x)是x!末尾 0 的数量。给定K问有多少个非负整数x具有f(x) K的性质。答案只可能取0或5两个值问题的难点在于如何判断给定的K是否可取。解法一二分搜索理论基础因子 5 的个数即末尾零的个数末尾零来自因子 10而因子 10 由质因数 2 和 5 相乘得到。由于 2 的个数永远多于 5 的个数n!末尾零的个数就等于[1, n]中所有整数所含质因数 5 的个数总和f(n) n/5 n/25 n/125 ...这正是 172 题的核心结论。在仓库中trailingZeroes函数以递归形式实现了这一公式见 0172.Factorial-Trailing-Zeroes/172. Factorial Trailing Zeroes.gofunc trailingZeroes(n int) int { if n/5 0 { return 0 } return n/5 trailingZeroes(n/5) }为什么搜索上界是 5·K每增加 5 个连续整数n!中就会多出至少一个质因数 5因此末尾零的个数至少增加 1。这意味着若存在某个x使得f(x) K那么最小的x一定小于5K于是[0, 5*K]是一个安全的二分搜索区间。二分搜索实现仓库中的解法一完整实现如下793. Preimage Size of Factorial Zeroes Function.go// 解法一 二分搜索 func preimageSizeFZF(K int) int { low, high : 0, 5*K for low high { mid : low (high-low)1 k : trailingZeroes(mid) if k K { return 5 } else if k K { high mid - 1 } else { low mid 1 } } return 0 }算法流程在[0, 5*K]上取中点mid调用trailingZeroes(mid)计算f(mid)若f(mid) K说明K可取直接返回5若f(mid) K说明零的个数过多缩小上界若f(mid) K说明零的个数不足扩大下界若整个区间内都找不到f(mid) K返回0。low (high-low)1的写法避免了(lowhigh)/2潜在的整型溢出问题是 Go 题解中的常用范式。为什么答案只可能是 0 或 5当n增加 5 以后因子 5 的个数必然又加一末尾零的个数会多 1 个甚至更多若增加后的数本身含多个因子 5例如 25、125末尾可能一次增加多个 0。因此对有效的K满足条件的n恰好落在一个长度为 5 的连续区间内答案是5对无效的K跳变点没有任何n与之对应答案是0。K的取值在5^n的分界线处会发生跳变导致部分值取不到。例如n ∈ [0, 5)时K 0n ∈ [5, 10)时K 1n ∈ [10, 15)时K 2n ∈ [15, 20)时K 3n ∈ [20, 25)时K 4n ∈ [25, 30)时K 6。因为25 5²一次提供了 2 个因子 5即 2 个 0所以K永远无法取值等于 5 —— 这正是示例 2 中K 5输出0的原因。后续的跳变点如K 31、K 156等也同理不可达。解法二数学方法变进制数判定核心观察解法二建立在两个结论之上n!末尾零的个数等于[1, n]中所有数的因子 5 的个数总和本题的答案一定只有 0 和 5分析见解法一。有了这两个结论就可以把问题转化为纯数学判定判断给定的K能否被表示出来。5 进制展开将n写成 5 进制形式n a0 a1·5 a2·5² ... am·5ᵐ其中aᵢ ∈ [0, 4]是 5 进制的各位数字。对f(n) n/5 n/25 n/125 ...做逐项展开并合并同类项所有有因子 5 的个数总和为K a1 6·a2 31·a3 ... Cm·am即K是aᵢ的加权和权重序列Cm满足递推关系Cm 5·C(m-1) 1由该递推还能推出通项公式本题使用递推形式更方便Cm (5ᵐ - 1) / 4验证C1 1C2 6C3 31C4 156……这一序列正是因子 5 个数总和在 5 进制下逐位展开时的进位基数。转成变进制数判定判断K是否能表示成上述数列的加权和等价于判断K是否能转化为以Cm为基的变进制数。若能表示且各位数字aᵢ都落在[0, 4]内则K有效答案为 5一旦某一位的系数达到 5即aᵢ 5说明该位发生了进位跳变则K无效答案为 0。到这一步问题就转化成了与 483 题「Smallest Good Base」同构的数论判定问题483 题的核心思路同样是从n的多项式/等比级数展开入手逐位校验系数可对照 0483.Smallest-Good-Base/483. Smallest Good Base.go 阅读。代码实现仓库中的解法二如下793. Preimage Size of Factorial Zeroes Function.go// 解法二 数学方法 func preimageSizeFZF1(K int) int { base : 0 for base K { base base*5 1 } for K 0 { base (base - 1) / 5 if K/base 5 { return 0 } K % base } return 5 }分阶段理解第一阶段for base K { base base*5 1 }从0开始不断执行base 5·base 1生成基数序列0, 1, 6, 31, 156, ...直到找到第一个不小于K的基数。第二阶段base (base - 1) / 5逐位回退基数递推关系的逆运算并检查K/base若K/base 5说明当前位系数为 5超出了 5 进制合法数字[0,4]的范围K处于跳变点直接返回0否则执行K % base剥掉当前位继续检查下一位。第三阶段若循环正常结束K降为 0 且从未出现系数 5说明K可被合法表示返回5。以K 5为例第一阶段得到base 6第二阶段base (6-1)/5 1K/base 5/1 5命中系数为 5 的条件返回0。以K 6为例base 6base 1K/1 6 ≠ 5K % 1得 0循环结束返回5。复杂度分析解法一二分搜索区间长度为5K二分约O(log K)轮每轮trailingZeroes迭代约O(log n)次。总体时间复杂度为O(log K · log K)空间复杂度O(log K)递归栈。解法二数学方法第一阶段与第二阶段都只迭代O(log₅ K)次时间复杂度O(log K)空间复杂度O(1)。由于K ≤ 10⁹两阶段最多各迭代十几轮运行开销极小。单元测试验证仓库为本题提供了单元测试793. Preimage Size of Factorial Zeroes Function_test.go覆盖了三个具有代表性的输入输入 K期望输出覆盖点05最小有效值0!到4!末尾均为 0 个零50跳变点25提供了 2 个因子 5K5不可达65跳变点之后重新可达的第一个有效值测试用例同时调用preimageSizeFZF解法一与preimageSizeFZF1解法二并断言解法二的结果与期望一致从而交叉验证两条解题路线的正确性。trailingZeroes在本题与 172 题中为同一实现复用关系也从源码结构上印证了793 题是 172 题逆过程的递进关系。延伸阅读正向问题172. Factorial Trailing Zeroes 题解掌握f(n) n/5 n/25 ...的推导同构问题483. Smallest Good Base 题解理解变进制/多项式展开的判定技巧解法一与解法二的完整源码793. Preimage Size of Factorial Zeroes Function.go。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解精讲：793. Preimage Size of Factorial Zeroes Function（阶乘末尾零的原像个数）
LeetCode-Go 题解精讲793. Preimage Size of Factorial Zeroes Function阶乘末尾零的原像个数【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 793 题「Preimage Size of Factorial Zeroes Function」展开讲解如何用 Go 求出满足f(x) K的非负整数x的个数其中f(x)是x!末尾零的个数。这道题是 172 题「Factorial Trailing Zeroes」的逆向加强版也是 483 题「Smallest Good Base」在数学上的同构问题。读完本文你将掌握两条可复现的求解路线基于二分搜索的通用解法解法一以及基于 5 进制展开与变进制数判定的数学解法解法二并看到它们在 LeetCode-Go 仓库中的完整 Go 实现与单元测试。题目描述设f(x)为x!末尾零的个数约定0! 1。例如f(3) 0因为3! 6末尾没有 0f(11) 2因为11! 39916800末尾有 2 个 0。给定整数K求有多少个非负整数x满足f(x) K。示例 1输入K 0 输出5 解释0!、1!、2!、3!、4! 的末尾都恰好有 0 个零。示例 2输入K 5 输出0 解释不存在任何 x 使得 x! 的末尾恰好有 5 个零。注意K是范围在[0, 10^9]内的整数。题目大意f(x)是x!末尾 0 的数量。给定K问有多少个非负整数x具有f(x) K的性质。答案只可能取0或5两个值问题的难点在于如何判断给定的K是否可取。解法一二分搜索理论基础因子 5 的个数即末尾零的个数末尾零来自因子 10而因子 10 由质因数 2 和 5 相乘得到。由于 2 的个数永远多于 5 的个数n!末尾零的个数就等于[1, n]中所有整数所含质因数 5 的个数总和f(n) n/5 n/25 n/125 ...这正是 172 题的核心结论。在仓库中trailingZeroes函数以递归形式实现了这一公式见 0172.Factorial-Trailing-Zeroes/172. Factorial Trailing Zeroes.gofunc trailingZeroes(n int) int { if n/5 0 { return 0 } return n/5 trailingZeroes(n/5) }为什么搜索上界是 5·K每增加 5 个连续整数n!中就会多出至少一个质因数 5因此末尾零的个数至少增加 1。这意味着若存在某个x使得f(x) K那么最小的x一定小于5K于是[0, 5*K]是一个安全的二分搜索区间。二分搜索实现仓库中的解法一完整实现如下793. Preimage Size of Factorial Zeroes Function.go// 解法一 二分搜索 func preimageSizeFZF(K int) int { low, high : 0, 5*K for low high { mid : low (high-low)1 k : trailingZeroes(mid) if k K { return 5 } else if k K { high mid - 1 } else { low mid 1 } } return 0 }算法流程在[0, 5*K]上取中点mid调用trailingZeroes(mid)计算f(mid)若f(mid) K说明K可取直接返回5若f(mid) K说明零的个数过多缩小上界若f(mid) K说明零的个数不足扩大下界若整个区间内都找不到f(mid) K返回0。low (high-low)1的写法避免了(lowhigh)/2潜在的整型溢出问题是 Go 题解中的常用范式。为什么答案只可能是 0 或 5当n增加 5 以后因子 5 的个数必然又加一末尾零的个数会多 1 个甚至更多若增加后的数本身含多个因子 5例如 25、125末尾可能一次增加多个 0。因此对有效的K满足条件的n恰好落在一个长度为 5 的连续区间内答案是5对无效的K跳变点没有任何n与之对应答案是0。K的取值在5^n的分界线处会发生跳变导致部分值取不到。例如n ∈ [0, 5)时K 0n ∈ [5, 10)时K 1n ∈ [10, 15)时K 2n ∈ [15, 20)时K 3n ∈ [20, 25)时K 4n ∈ [25, 30)时K 6。因为25 5²一次提供了 2 个因子 5即 2 个 0所以K永远无法取值等于 5 —— 这正是示例 2 中K 5输出0的原因。后续的跳变点如K 31、K 156等也同理不可达。解法二数学方法变进制数判定核心观察解法二建立在两个结论之上n!末尾零的个数等于[1, n]中所有数的因子 5 的个数总和本题的答案一定只有 0 和 5分析见解法一。有了这两个结论就可以把问题转化为纯数学判定判断给定的K能否被表示出来。5 进制展开将n写成 5 进制形式n a0 a1·5 a2·5² ... am·5ᵐ其中aᵢ ∈ [0, 4]是 5 进制的各位数字。对f(n) n/5 n/25 n/125 ...做逐项展开并合并同类项所有有因子 5 的个数总和为K a1 6·a2 31·a3 ... Cm·am即K是aᵢ的加权和权重序列Cm满足递推关系Cm 5·C(m-1) 1由该递推还能推出通项公式本题使用递推形式更方便Cm (5ᵐ - 1) / 4验证C1 1C2 6C3 31C4 156……这一序列正是因子 5 个数总和在 5 进制下逐位展开时的进位基数。转成变进制数判定判断K是否能表示成上述数列的加权和等价于判断K是否能转化为以Cm为基的变进制数。若能表示且各位数字aᵢ都落在[0, 4]内则K有效答案为 5一旦某一位的系数达到 5即aᵢ 5说明该位发生了进位跳变则K无效答案为 0。到这一步问题就转化成了与 483 题「Smallest Good Base」同构的数论判定问题483 题的核心思路同样是从n的多项式/等比级数展开入手逐位校验系数可对照 0483.Smallest-Good-Base/483. Smallest Good Base.go 阅读。代码实现仓库中的解法二如下793. Preimage Size of Factorial Zeroes Function.go// 解法二 数学方法 func preimageSizeFZF1(K int) int { base : 0 for base K { base base*5 1 } for K 0 { base (base - 1) / 5 if K/base 5 { return 0 } K % base } return 5 }分阶段理解第一阶段for base K { base base*5 1 }从0开始不断执行base 5·base 1生成基数序列0, 1, 6, 31, 156, ...直到找到第一个不小于K的基数。第二阶段base (base - 1) / 5逐位回退基数递推关系的逆运算并检查K/base若K/base 5说明当前位系数为 5超出了 5 进制合法数字[0,4]的范围K处于跳变点直接返回0否则执行K % base剥掉当前位继续检查下一位。第三阶段若循环正常结束K降为 0 且从未出现系数 5说明K可被合法表示返回5。以K 5为例第一阶段得到base 6第二阶段base (6-1)/5 1K/base 5/1 5命中系数为 5 的条件返回0。以K 6为例base 6base 1K/1 6 ≠ 5K % 1得 0循环结束返回5。复杂度分析解法一二分搜索区间长度为5K二分约O(log K)轮每轮trailingZeroes迭代约O(log n)次。总体时间复杂度为O(log K · log K)空间复杂度O(log K)递归栈。解法二数学方法第一阶段与第二阶段都只迭代O(log₅ K)次时间复杂度O(log K)空间复杂度O(1)。由于K ≤ 10⁹两阶段最多各迭代十几轮运行开销极小。单元测试验证仓库为本题提供了单元测试793. Preimage Size of Factorial Zeroes Function_test.go覆盖了三个具有代表性的输入输入 K期望输出覆盖点05最小有效值0!到4!末尾均为 0 个零50跳变点25提供了 2 个因子 5K5不可达65跳变点之后重新可达的第一个有效值测试用例同时调用preimageSizeFZF解法一与preimageSizeFZF1解法二并断言解法二的结果与期望一致从而交叉验证两条解题路线的正确性。trailingZeroes在本题与 172 题中为同一实现复用关系也从源码结构上印证了793 题是 172 题逆过程的递进关系。延伸阅读正向问题172. Factorial Trailing Zeroes 题解掌握f(n) n/5 n/25 ...的推导同构问题483. Smallest Good Base 题解理解变进制/多项式展开的判定技巧解法一与解法二的完整源码793. Preimage Size of Factorial Zeroes Function.go。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考