LightOj 1138 Trailing Zeroes (III)

题目描述：

　　假设有一个数n，它的阶乘末尾有Q个零，现在给出Q，问n最小为多少？

解题思路:

　　由于数字末尾的零等于min（因子2的个数，因子5的个数），又因为2<5,那么假设有一无限大的数n，n=2^x=5^y，可知x<<y。

所以我们可以直接根据因子5的个数，算阶乘末尾的零的个数。1<=Q<=10^8,所以可以用二分快速求解。

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 #define LL long long
 8 LL find_zeros (LL n)
 9 {
10     LL ans = 0;
11     while (n)
12     {
13         ans += n / 5;
14         n /= 5;
15     }
16     return ans;
17 }
18 int main ()
19 {
20     LL t, n, l = 1;
21     scanf ("%lld", &t);
22     while (t --)
23     {
24         scanf ("%lld", &n);
25         LL low, high, mid;
26         low = 4;
27         high = 500000000;
28         while (low <= high)
29         {
30             mid = (low + high) / 2;
31             LL   num = find_zeros(mid);
32             if (num < n)
33                 low = mid + 1;
34             if (num >= n)//求出来的n要是最小的，所以这里不能直接返回
35                 high = mid - 1;
36         }
37         if (find_zeros(low) == n)
38             printf ("Case %lld: %lld
", l++, low);
39         else
40             printf ("Case %lld: impossible
", l++);
41     }
42     return 0;
43 }

本文为博主原创文章，未经博主允许不得转载。