Light OJ 1138 Trailing Zeroes (III)(n！中素数p的幂有关问题)

Light OJ 1138 Trailing Zeroes (III)(n！中素数p的幂问题)

题意：求n，满足n！的末尾有Q个0

数据范围：T (≤ 10000), denoting the number of test cases.

Each case contains an integer Q (1 ≤ Q ≤ 10⁸) in a line.

思路：n！中素数p的幂公式： [n/p]+[n/p^2]+[n/p^3]+……

证明在http://www.cnblogs.com/openorz/archive/2011/11/14/2248992.html详述

n！中的0的个数即是n！中因数（2，5）的对数，由于是n！，显然5的因数比2少，所以Q=因数5的个数

求幂是logn的算法，可以二分答案n，所以复杂度是O(T*(logn)^2)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int n;
int f(int x)
{
    int ans=0;
    while(x/5)
    {
        ans+=x/5;
        x/=5;
    }
    return ans;
}
int Bin()
{
    int l=1,r=(int)5e8;
    int t;
    bool flag=0;
    while(r-l>1)
    {
        int mid=(l+r)>>1;
        t=f(mid);
        if(t>=n)
        {
            if(flag==0) flag = (t==n);
            r=mid;
        }
        else l=mid;
    }
    if(flag==0||r==(int)5e8) r=-1;
    return r;
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++)
    {
        scanf("%d",&n);
        int ans=Bin();
        if(ans==-1) printf("Case %d: impossible\n",cas);
        else printf("Case %d: %d\n",cas,ans);
    }
    return 0;
}