Sunday, 19 June 2016

Light Oj 1138 Trailing Zeroes (III)

#include <bits/stdc++.h>
using namespace std ;
typedef long long ll;
ll count_5(ll num)
{
    ll pow_5=5,counter=0;
    while(pow_5<=num)
    {
        counter+=num/pow_5;
        pow_5*=5;
    }
    //cout<<counter<<endl;
    return counter;
}
ll binary_s(ll n)
{
    int low=0,high=1000000000,mid,ans=0;
    while (low<=high)
    {
        mid=(low+high)/2 ;
        ll tmp=count_5(mid);
        if (tmp<n)
            low=mid+1;
        else if(tmp>n)
            high=mid-1;
        else
        {
            ans=mid;
            high=mid-1;
        }
    }
    return ans ;
}
int main ()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for (k=1;k<=test;k++)
    {
        cin>>n;
        ll ans=binary_s(n);
        if(ans==0)
            cout<<"Case "<<k<<": "<<"impossible"<<endl;
        else
            cout<<"Case "<<k<<": "<<ans<<endl;
    }
    return 0 ;
}

No comments:

Post a Comment