[LightOJ] Problem 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! = 12…*N. For example, 5! = 120, 120 contains one zero on the trail.

Time Limit: 2 second(s)
Memory Limit: 32 MB

Input

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

Each case contains an integer Q (1 ≤ Q ≤ 10^8) 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

Output for Sample Input

Case 1: 5
Case 2: 10
Case 3: impossible

Code

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		
		if (t < 1 || t > 10000)
			return;
		
		for (int i = 1; i <= t; i++) {
			int x = sc.nextInt();
			
			if (x < 1 || x > Math.pow(10, 8))
				return;
			
			long result = binarySearch(1, Long.MAX_VALUE, x);
			
			if (result != -1)
				System.out.println("Case " + i + ": " + result);
			else
				System.out.println("Case " + i + ": impossible");
		}
	}
	
	private static long trailingZeroes(long n) {
		return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
	}
	
	private static long binarySearch(long left, long right, long key) {
		while (left <= right){
			long mid = (left + right) / 2;
			
			if (trailingZeroes(mid) == key && trailingZeroes(mid - 1) < key) 
				return mid;
			else if (trailingZeroes(mid) < key) 
				left = mid + 1;
			else 
				right = mid - 1;
		}
		
		return -1;
	}
}