| 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 ≤ 108) 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 |
今天脑残了。。。。。。
#include <map> #include <set> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <iostream> #include <stack> #include <cmath> #include <vector> #include <cstdlib> //#include <bits/stdc++.h> #define space " " using namespace std; typedef long long LL; //typedef __int64 Int; typedef pair<int,int> paii; const int INF = 0x3f3f3f3f; const double ESP = 1e-5; const double Pi = acos(-1); const int MOD = 1e9+5; const int MAXN = 1e5; bool flag ; bool judge(int x, int y) { int f = 5; int sum = 0; while (f <= x) { sum = sum + x/f; f = f*5; } if (sum == y) flag = true; return sum >= y; } int main() { int t, n; int cnt = 0; scanf("%d", &t); while (t--) { scanf("%d", &n); int ans; flag = false; int lb = 0, ub = 1e9; while (ub >= lb) { int mid = (ub + lb) >> 1; if (judge(mid, n)) { ans = mid; ub = mid - 1; } else lb = mid + 1; } if (flag) printf("Case %d: %d ", ++cnt, ans); else printf("Case %d: impossible ", ++cnt); } return 0; }