LightOJ-1138 Trailing Zeres（III）（サブサーチ）
2141 ワード
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=88668#problem/H
Trailing Zeroes（III）
Description
You task is to find minimal natural number N，so that N！ contains exactly Q ゼロスon the trol in decimal notation.As you know N！=1＊2＊＊＊N.For example、5！=120 contains one zero on the trill.
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のsolution is found then print 'impossible
Sample Input
3
1
2
5
Sample Output
Case 1:5
Case 2:10
Case 3:impossible
テーマの説明:
一つの数nがあると仮定して、その階乗の末尾にQ個のゼロがあります。今Qを与えます。nが一番小さいのはいくらですか？
問題解決の考え方：
数字の末尾のゼロはmin（因子2の個数、因子5の個数）に等しいため、また2<5のため、無限大の数n、n=2^x=5^yがあると仮定して、x<ですから、因子5の個数によって、階乗の末尾のゼロの個数を直接計算します。1<=Q<=10^8ですので、2分で速く解決できます。
Trailing Zeroes（III）
Description
You task is to find minimal natural number N，so that N！ contains exactly Q ゼロスon the trol in decimal notation.As you know N！=1＊2＊＊＊N.For example、5！=120 contains one zero on the trill.
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のsolution is found then print 'impossible
Sample Input
3
1
2
5
Sample Output
Case 1:5
Case 2:10
Case 3:impossible
テーマの説明:
一つの数nがあると仮定して、その階乗の末尾にQ個のゼロがあります。今Qを与えます。nが一番小さいのはいくらですか？
問題解決の考え方：
数字の末尾のゼロはmin（因子2の個数、因子5の個数）に等しいため、また2<5のため、無限大の数n、n=2^x=5^yがあると仮定して、x<
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <limits>
#include <queue>
#include <stack>
#include <vector>
#include <map>
using namespace std;
#define N 505
#define INF 0x3f3f3f3f
#define PI acos (-1.0)
#define EPS 1e-8
#define met(a, b) memset (a, b, sizeof (a))
long long findzeros (long long num);
int main ()
{
long long t, n, flag=1;
scanf ("%lld", &t);
while (t--)
{
scanf ("%lld", &n);
long long mid, l = 4, r = 500000000;
while (l <= r)
{
mid = (l + r) / 2;
long long num = findzeros (mid);
if (num < n)
l = mid + 1;
if (num >= n)
r = mid - 1;
}
if (findzeros (l) == n)
printf ("Case %lld: %lld
", flag++, l);
else printf ("Case %lld: impossible
", flag++);
}
}
long long findzeros (long long num)
{
long long ans = 0;
while (num)
{
ans += num / 5;
num /= 5;
}
return ans;
}