题目链接: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)是单调的,于是自然思考二分

寻找上界:

即:

于是得到上界:5k

寻找下界:

即:

于是得到下界: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;
    }
};