LightOJ - 1138 Trailing Zeroes (III)（n的阶乘结尾0的个数+二分）

传送门

题目大意

给出$q$，我们需要求出最小的$n$使得$n!$结尾有$q$个$0$

题目大意

考虑$n$的阶乘结尾$0$的个数，实际上就是看最后乘了多少个$10$，也就是将$n!$质因数分解得出的$2^x{5}^y$，结尾$0$的个数就是min{x,y}min\{x,y\}min{ x,y}，手推前几个阶乘，不难发现$x>y$一定成立，因此我们只需考虑$5$的个数。对于$n!$内含有多少质数的乘积，这是一个比较巧妙的数论知识：

• 首先看第一层，也就是只含一个以上$5$的数的个数，显然是$n/5$
• 然后看第二层，因为阶乘是前$n$个数相乘而不是考虑前面的每个数，那么第一层考虑的只含一个$5$的数中也包含了含有两个$5$以上的，因此含有两个以上$5$的个数为$n/(n/5)$
• 以此类推，每次累加$n/5$，然后$n/=5$即可

随着$n$的增大，显然其阶乘中含有$5$的个数是非递减的，那么考虑二分，手推一下不难发现左边界为$1$，右边界为$5?q$。还有就是手玩一下不难发现每$5$个数其含有$5$的个数是相等的，答案需要求最小的，实际上如果存在那么一定是$5$的倍数，我们采用如下的二分形式：

while(l + 10 < r){
    ....
}

代码

//
// Created by Happig on 2020/10/22
//
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define ENDL "\n"
#define lowbit(x) (x&(-x))
#define mkp(x, y) make_pair(x,y)
#define mem(a, x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double dinf = 1e300;
const ll INF = 1e18;
const int Mod = 1e9 + 7;
const int maxn = 5e5 + 10;int cal(ll n) {
    int ans = 0;while (n) {
    ans += n / 5;n /= 5;}return ans;
}int main() {
    //freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);//ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T, kase = 0;ll q;cin >> T;while (T--) {
    cin >> q;ll l = 1, r = q * 5;while (l + 10 < r) {
    ll mid = (l + r) / 2;if (cal(mid) < q) {
    l = mid + 1;} else r = mid;}int ans = -1;for (int i = l; i <= r; i++) {
    if (cal(i) == q) {
    if (ans < 0) ans = i;else ans = min(ans, i);}}cout << "Case " << ++kase << ": ";if (ans < 0) cout << "impossible" << ENDL;else cout << ans << ENDL;}return 0;
}