题目大意:给你t个输入,每个输入给你一个数N,问你最小一个数的阶乘末尾的0有n的数字是多少,比如5!=120末尾有一个0,不存在这种数字输出impossible
思路:当时校队比赛做的题目,还是太菜做了三小时没做明白,不过结束后听师兄说二分回去花17分钟就做出来了。
首先,要明白一个数每有1个5就会有一个0
可以这么思考:5的阶乘为12345,每有一个5,前面都有偶数和它对应形成10
所以一个数除以5就说明了这个数最少有几个0
但是还有没有特殊情况呢?
有的,比如25的阶乘,最后的一个数25是5*5的乘积,那么前面有两个偶数和它对应,这时候就会多出来一个5
所以25的阶乘末尾0有6个
那么如果你知道一个数的阶乘末尾0的计算方法就出来了
直接把这个数一直除以5,把除以5的数量全部加起来就是末尾0的答案了(全部都是乘除答案)
可惜这题是反过来求数的阶乘
这时候就要利用二分进行快速查找求解了
因为前面全部都是整除的
反推很难找到方法(反正我是想了3小时找不到方法)
那么代码就出来啦
代码:

#include 
#include 
using namespace std;
int solve(int x){
    int cnt=0;
    x*=5;
      while(x){//求末尾有多少个0,看答案*5的结果对不对
          x/=5;
        cnt+=x;
      }
     return cnt;
}
int main()
{
    int t;
    cin>>t;
            int i=1;
    while(t--){
        int n;
        cin>>n;
        int l=0,r=n;
        int mid;
        while(l<=r){//二分
            mid=(l+r)/2;
            if(solve(mid)<n){
                l=mid+1;
            }else {
                if(solve(mid)==n)break;//通过这个判断是不是impossible
                else r=mid-1;
                }
        }
        printf("Case %d: ",i++);
        if(solve(mid)==n)cout<<mid*5<<endl;
        else cout<<"impossible"<<endl;
    }
    return 0;
}