【LeetCode每日一题】793.阶乘函数后 K 个零

题目链接：https://leetcode.cn/problems/preimage-size-of-factorial-zeroes-function/

题目难度：困难

题意

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

题解：二分+数学

首先需要了解前备知识：LeetCode 172：阶乘后的零

对于整数x！中末尾零的数量为：f(x)，其中

$$f(x)=\Sigma_{k=1}^{\infty}\lfloor \frac{x}{5^k} \rfloor$$

同时不难发现f(x)是单调的，于是自然思考二分

寻找上界：

$$f(x)=\Sigma_{k=1}^{\infty}\lfloor \frac{x}{5^k} \rfloor>=\lfloor\frac{x}{5} \rfloor$$

即：

$$f(5k)>=\lfloor\frac{5k}{5} \rfloor=k$$

于是得到上界：5k

寻找下界：

$$f(x)=\Sigma_{k=1}^{\infty}\lfloor \frac{x}{5^k} \rfloor<=\Sigma_{k=1}^{\infty}\frac{x}{5^k}<=\frac{x}{4}$$

即：

$$f(4k)<=\frac{4k}{4}=k$$

于是得到下界：4k

同时参考此题解：https://leetcode.cn/problems/preimage-size-of-factorial-zeroes-function/solution/by-vclip-9quy/，可以知道最终结果要么是5，要么是0。

C++代码

class Solution {
public:
    typedef long long ll;
    ll f(ll x){
        ll ans=0;
        while(x){
            x/=5;ans+=x;
        }
        return ans;
    }
    int preimageSizeFZF(int k) {
        ll l=4ll*k;
        ll r=5ll*k;
        while(l<r){
            ll mid=(l+r)/2;
            if(f(mid)<k){
                l=mid+1;
            }else{
                r=mid;
            }
        }
        return f(l)==k?5:0;
    }
};