Trailing Zeroes (III)

题目

You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you know N! = 12...*N. For example, 5! = 120, 120 contains one zero on the trail.
就是找最小的N，使得N！末尾有x个0，输出N，若不存在输出impossible

分析

其实这个题上个暑假就做过，但是当时求一个N！末尾0的个数怎么推导的没有去细想。这里我给出其规律。
代码是这样的

int judge(ll x){
    ll cnt = 0;
    while(x){
        cnt += x/5;
        x/=5;
    }
    return cnt;
}

对于N!,2的个数一定是大于5的个数的，比如1，2，3，4，5，6，7，8，9，10，2可以有2，4，6，8，10，分解出来，5只能由5，10分解出来。2的倍数大于5的倍数。然后我们有一个5，肯定能拿出一个2与之匹配，末尾就产生了一个0，所以我们可以把求解N!末尾0的个数，转而去求N!中5的个数

5 10 15 20 25 30 35 40 45 50 。。。。。100 105 110 115 120 125。。。
能分解出1个5的：5 10 15 20 。。。
能分解出2个5的：25 50 75 100。。。
能分解出3个5的：125 250 375 500
能分解出4个5的：625
可以发现每隔5隔位置，5的个数就会增长1个。
所以在代码中，每一次除以5，就相当于把所有数5的因子个数减1，之前能分解出2个5的，减去一个后，只留一个了，能分解出3个的，还留下2个。而此时还能分解出5的数有N/5个，依次迭代就行了。

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int T,N;

int judge(ll x){
    ll cnt = 0;
    while(x){
        cnt += x/5;
        x/=5;
    }
    return cnt;
}
int main(){
    cin>>T;
    int kase = 0;
    while(T--){
        scanf("%d",&N);
        ll l = 1,r = (ll)1e9,mid,res = -1;
        while(l<r){
            mid = (l+r)/2;
            ll t = judge(mid);
            if(t<N) l = mid+1;
            else if(t>N) r = mid-1;
            else {
                res = mid;
                break;
            }
        }
        if(res == -1) printf("Case %d: impossible\n",++kase);
        else printf("Case %d: %lld\n",++kase,res-res%5);
    }
    return 0;
}