1
#define ll long long
2
class Solution {
3
 public:
4
  bool check(ll num, int k) {
5
    ll start = 5;
6
    ll ans = 0;
7
    while (start <= num) {
8
      ans += (num / start);
9
      start *= 5;
10
    }
11
    return ans <= k;
12
  }
13
  ll get(int k) {
14
    ll lo = 1;
15
    ll hi = 1e18;
16
    ll mid, res(1e18);
17
    while (lo <= hi) {
18
      mid = (lo + hi) / 2;
19
      if (check(mid, k)) {
20
        lo = mid + 1;
21
        res = mid;
22
      } else
23
        hi = mid - 1;
24
    }
25
    return res;
26
  }
27
  int preimageSizeFZF(int k) {
28
    if (k == 0) return 5;
29
    return (get(k) - get(k - 1));
30
  }
31
};