solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

class Solution {
   public:
    int preimageSizeFZF(int k) {
        long long maxn = 5e9;        
        vector<long long> five;
        long long now = 1;
        while (now <= maxn) {
            five.push_back(now);
            now *= 5;
        }
        debug(five.size());

        long long l = 0, r = maxn;
        
        auto get_num = [&](long long val) -> long long {
            long long num = 0;

            for (int i = 0; i < five.size(); i++) {
                if (five[i] > val) break;
                num += val / five[i];
            }
            return num;
        };

        while (l <= r) {
            long long mid = l + r >> 1;
            long long num = get_num(mid);
            if (num == k) {
                return 5;
            } else if (num > k) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return 0;
    }
};