Light oj 1138 - 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! = 1*2*…*N. For example, 5! = 120, 120 contains one zero on the trail.

Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.

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

Output
For each case, print the case number and N. If no solution is found then print ‘impossible’.

Sample Input
3
1
2
5
Sample Output
Case 1: 5
Case 2: 10
Case 3: impossible

这道题 想了 好长时间 ，到最后 答案是 算出来啦 但是 不是超时， 就是 memery 超啦，唉。。。 不过 最终 还是 会写啦 。先说一下 题目的 大意，就是 给你一个 数 表示 某个数 N 结成后 得到的 值的 后面 number of all behand zero, 就是 末尾 零的个数， 然后 让你写一个 程序 给你 零的 个数 然后 输出 那个 数 。 了解题目的大意之后 简单的 思考一下 感觉 题目的意思 不是很难， 但是 请仔细的看一下数据的范围 ，给的 时间的 2 秒，如果 用 一般的方法写的话 一定会超时 的 ，或者 内存超限，简单的思考一下 ，乘法可以得到零的 只有 偶数 和 5 相乘 然而 n！ 之中 偶数的个数 显然是 多的 用不完 啦 ，那么 零的 个数 就是 与 5 的个数 有关 啦， 而且 一个5 只能得到 一个零 ， 所以 零的 个数 = N！中 5 的个数，好啦 现在 的问题就是 找 一个数 n 含有 几个5 啦。下面程序里 有一个函数 ，是 求解 一个数 对应 阶乘 数 中 零的 个数 ， 原理 大概说一下 ： 他是 先找 n！ 中 1 =》 n 中 可以 被 5 整除的 数的 个数 ，然后 在 计算 可以 被 5*5 整除的数的 个数 ，保证 除数 不大于 被除数 N ， 最后 将 找的的 个数 累加 起来 就是 对应 零的 个数 啦 列一个 例子： n = 100；
1 =》 100 中 可以 被 5 整除的 有 5，10，15，……，85， 90， 95， 100， 能够 被 5*5 整除的 数 为： 25， 50， 75， 100， 所以 100！ 中 末尾 零的 个数 为 20 + 4 = 24 个； 这其中 为了 减少时间 ，没有 用 循环 而是用的 线段树 相当于 二分 法查找 ，找出 答案 ；具体过程 看 下面的代码；

#include <cstdio>  
#include <iostream>  
#include <algorithm>  
#include <cmath>  
#include <cstring>  
#include <stack>  
using namespace std;  
long long n;  
long long get_5(long long n)  
{  
    long long ans=0;  
    long long five=5;  
    while(n>=five)  
    {  
        ans+=n/five;  
        five*=5;  
    }  
    return ans;  
}  
long long solve(long long l,long long r)  
{  
    long long mid=(l+r)/2;  
    long long tmp=get_5(mid);  
    if(l==r)  
    {  
        if(get_5(mid)==n)  
            return mid;  
        else  
            return -1;  
    }  
    if(tmp<n)  
    {  
        return solve(mid+1,r);  
    }  
    else if(tmp>n)  
    {  
        return solve(l,mid);  
    }  
    else  
        return mid;  

}  
int main()  
{  
    int t;  
    scanf("%d",&t);  
    for(int cases=1;cases<=t;cases++)  
    {  
        scanf("%lld",&n);  
        long long ans=solve(0,1000000000000);  
        if(ans==-1)  
            printf("Case %d: impossible\n",cases);  
        else  
        {  
            while(get_5(ans-1)==n)  // 题目要求 最小的 数
                ans--;  
            printf("Case %d: %lld\n",cases,ans);  
        }  
    }  
    return 0;  
}