Light oj 1138 -Trailing Zeroes (III)

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! = 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
3
1
2
5
Sample Output
Case 1: 5
Case 2: 10

Case 3: impossible

解题思路：通过判断因子5的个数来判断阶乘末尾0的个数，通过二分法找出所需值。

        本来打算求出n的阶乘，但是n的阶乘所得的数太大，会超过int甚至是longlong的范围，所以不能用求n的阶乘的方法。

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
long long slove(long long n)//定义一个long long 的结构体，其中自定义n的类型为long long
{
    long long ans = 0;
    while(n)//n在这里被当作了一个条件,判断n的真假 
	 {
         ans += n/5;
         n /= 5;
     }
        return ans;
 }
 
 int main()
 {
     int t, p = 1;
 
     scanf("%d", &t);
     while(t--)
     {
         long long n;
         scanf("%lld", &n);
         long long mid, left = 4, right = 500000000;
 
         while(left <= right)    // 二分查找
         {
             mid = (left+right)/2;
             long long num = slove(mid);
             if(num >= n)
                right = mid-1;
             else
                 left = mid+1;
         }
         if(slove(left) == n)
             printf("Case %d: %lld\n", p++, left);
         else
             printf("Case %d: impossible\n", p++);
     }
     return 0;
 }

#include<iostream>是标准的C++头文件，任何符合标准的C++开发环境都有这个头文件。

在VC中编程的同时要注意要添加:using namespace std;

在C++中，输入输出流被定义为类。C++的I/O库中的类称为流类(stream class)。用流类定义的对象称为流对象。