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,所以可以用二分快速求解。

代码：

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 #define LL long long

 LL find_zeros (LL n)

 {

     LL ans = ;

     while (n)

     {

         ans += n / ;

         n /= ;

     }

     return ans;

 }

 int main ()

 {

     LL t, n, l = ;

     scanf ("%lld", &t);

     while (t --)

     {

         scanf ("%lld", &n);

         LL low, high, mid;

         low = ;

         high = ;

         while (low <= high)

         {

             mid = (low + high) / ;

             LL   num = find_zeros(mid);

             if (num < n)

                 low = mid + ;

             if (num >= n)//求出来的n要是最小的，所以这里不能直接返回

                 high = mid - ;

         }

         if (find_zeros(low) == n)

             printf ("Case %lld: %lld\n", l++, low);

         else

             printf ("Case %lld: impossible\n", l++);

     }

     return ;

 }

巴特西

LightOj 1138 Trailing Zeroes (III)

最新文章

热门文章