/*
 * @lc app=leetcode.cn id=793 lang=cpp
 *
 * [793] 阶乘函数后 K 个零
 */

// @lc code=start
class Solution {
public:
    long findZero(long n) {
        long res = 0;
        for (long d = n; d / 5 > 0; d = d / 5) {
            res += d / 5;
        }
        return res;
    }

    int preimageSizeFZF(int k) {
        return (int)(right_bound(k) - left_bound(k) + 1);
    }

    long left_bound(int target) {
        long lo = 0, hi = LONG_MAX;
        while (hi > lo) {
            long mid = lo + (hi - lo) / 2;
            if (findZero(mid) >= target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    long right_bound(int target) {
        long lo = 0, hi = LONG_MAX;
        while (hi > lo) {
            long mid = lo + (hi - lo) / 2;
            if (findZero(mid) <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo - 1;
    }
};
// @lc code=end