题面

大秦为你打开题目传送门 （看不了的就看下面吧）

找出最小的自然数据 $N$ ，使得 $N!$ 刚好有 $Q$ 个后缀零。$N!=1\times2\times…\times N$ 例如 $5!=1\times2\times3\times4\times 5=120$, $120$有 $1$ 个后缀 $0$ 。

题意

显而易见的，$N$ 越大，阶乘的后缀零越多，所以这是一个二分题。

二分答案 $N$ ，对于它数 $1$ 至 $N$ 有几个因子 $5$ 。显然，$1$ 至 $N$ 中 $5$ 的倍数是 $\lfloor N/5\rfloor$ 但是，这还不够，因为有一些数字有多个因数 $5$ 。所以要把那些 $5$ 的倍数拿出来反复如上操作，如下图。

我们设 $N = 30$ ，然后做第一个除以 $5$ 的操作，答案是 $6$ 。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
N N N N Y N N N N Y N N N N Y
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
N N N N Y N N N N Y N N N N Y

然后 $6$ 再进行除以 $5$ 操作，意义是把只有一个因子 $5$ 的数删去，两个及以上因子 $5$ 的数字统计，因为在都是 $5$ 的倍数下，$25$ 倍数也是 $5$ 个 $5$ 个来的。也就是下表：

5 10 15 20 25 30
N N N N Y N

接下来对于 $1$ 进行除以 $5$ 操作，意义是在都是 $25$ 的倍数中，$125$ 的倍数是每 $5$ 个出现一次。

最终答案就是， $6 + 1 + 0 = 7$ 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;

int Q;

void Input() {
    scanf("%d", &Q);
}

int Check(int mid) {
    long long ans = 0;
    while (mid) {
        ans += mid / 5;
        mid /= 5;
    }
    return ans;
}

void Work() {
    int l = 0, r = 1e9, best = -1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (Check(mid) >= Q) {
            r = mid - 1;
            best = mid;
        }
        else {
            l = mid + 1;
        }
    }
    if (Check(best) == Q) printf("%d\n", best);
    else printf("impossible\n");
}

int main() {
    int T, ca = 1;
    scanf("%d", &T);
    while (T--) {
        Input();
        printf("Case %d: ", ca++);
        Work();
    }
    return 0;
}