Trailing Zeroes (III) LightOJ - 1138 二分+找规律

Time Limit: 2 second(s)

Memory Limit: 32 MB

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 ≤ 10⁸) in a line.

Output

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

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

题意：求出现一个最小的数的阶乘满足末尾有连续q个0。

思路：一个最小的数末尾要出现0一定要是能被5或10整除的，0的连续长度与数组大小正相关，故二分数字得解。

 #include<set>
 #include<map>
 #include<stack>
 #include<cmath>
 #include<queue>
 #include<cstdio>
 #include<string>
 #include<cstring>
 #include<iostream>
 #include<limits.h>
 #include<algorithm>
 #define mem(a,b) memset(a,b,sizeof(a))
 using namespace std;
 const int INF=1e9;
 typedef unsigned long long ll;
 typedef long long LL;
 int main()
 {
     int T,cases=;
     scanf("%d",&T);
     while(T--)
     {
         int q;
         LL ans=-;
         scanf("%d",&q);
         int l=,r=q*,mid;//为什么右端点是q*5，因为q*5>=ans.想一想为什么（hint：刚才那个序列。。。）
         while(l<=r)
         {
             mid=(l+r)/;
             int m=mid,wu=,count=;
             while(m>=wu)
             {
                 int p=m;
                 p/=wu;
                 count+=p;
                 wu*=;
             }
             if(count==q)
             {
                 ans=mid;
                 break;
             }
             else if(count>q)
                 r=mid-;
             else
                 l=mid+;
         }
         if(ans==-)
             printf("Case %d: impossible\n",cases++);
         else
             printf("Case %d: %lld\n",cases++,ans/*);
     }
 }

代码转自(https://blog.****.net/duan_1998/article/details/72566106)