793.阶乘函数后K个零

链接：793.阶乘函数后K个零
难度：Hard
标签：数学、二分查找
简介：给定 k，找出返回能满足 f(x) = k 的非负整数 x 的数量。

题解 1 - cpp

• 编辑时间：2022-08-28
• 内存消耗：5.8MB
• 编程语言：cpp
• 解法介绍：层序遍历。

class Solution {
public:
    int preimageSizeFZF(int k) {
        return help(k + 1) - help(k);
    }
    long long help(int k) {
        long long l = 0, r = 5LL * k;
        while (l < r) {
            long long mid = (l + r) / 2;
            if (get_cnt(mid) >= k) r = mid;
            else l = mid + 1;
        }
        return l;
    }
    int get_cnt(int num) {
        int cnt = 0;
        while (num) {
            cnt += num / 5;
            num /= 5;
        }
        return cnt;
    }
};