Trailing Zeroes (III) 数学思维+二分-蒲公英云

Trailing Zeroes (III) 数学思维+二分

港控/mmm° 2024-04-17 05:58 157阅读 0赞

题目链接：https://vjudge.net/problem/POJ-1426

/********* 二分查找 n! 末尾有几个零， 其实就是 1～n中 有几个因子 5和因子2， 因为只素因子 5 和2的乘积 == 10 ， 才会使末尾加一个0， （因为n内 2的因子个数肯定比5多 所以只考虑5就行了） ***********/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T, n, cnt = 0;
int flag;
ll check(ll x)// 查找 查找不大于x的所有数， 有几个因子5
{ 
    ll ans = 0;
    while(x)
    { 
        ans+= x/5;// x内有 x/5个5的倍数
        x/=5;
    }
    return ans;
}
int main()
{ 
    ios_base::sync_with_stdio(false);
    cin>>T;
    while(T--)
    { 
        cnt++;
        cin>>n;
        ll ans = -1;
        ll L = 0, R = 1000000000;// 为什么右端点 从1e9开始， 因为1e9内 有2e8个5的倍数 所以肯定满足题目 Q = 1e8的要求
        flag = 0;
        while(L <= R)
        { 
            ll mid = (L+R)/2;
            ll cnt2 =check(mid);
            if(cnt2 > n)
            { 
                R = mid-1;
                ans = mid;
            }
            else
            { 
                L = mid+1;
            }
            if(cnt2 == n)
            { 
                flag = 1;
                ans = mid;
                break;
            }
        }
        if(flag)cout<<"Case "<<cnt<<": "<<ans-ans%5<<endl;// 最小 结尾为q个0，一定是5的倍数的阶乘， 所以 ans - ans%5.
        else cout<<"Case "<<cnt<<": "<<"impossible"<<endl;
    }
    return 0;
}