LightOJ – 1138 Trailing Zeroes (III)

题目链接

给一个整数Q(1<=Q<=10^8),求最小的N使N!的后缀有Q个0.

N!有多少个因子5,后缀就有多少个0,因为前面一定有足够多的因子2来与之相乘. 于是可以对N!求因子5的个数来确定后缀有几个0,求法可参考 阶乘分解

对N可确定一个范围,然后二分答案求解,注意最后得到的N,其5的因子个数可能是大于Q的.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int getCnt(int n){
    int cnt=0;
    while(n){
        cnt+=n/5;
        n/=5;
    }
    return cnt;
}

int main() {
  int T,kase=0;
  //freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
  scanf("%d",&T);
  while(T--){
     int Q;
     cin>>Q;
     int l=5,r=Q*5;
     while(l<r){
         int mid=(l+r)/2;
         if(getCnt(mid)<Q) l=mid+1;
         else r=mid;
     }
     printf("Case %d: ",++kase);
     if(getCnt(r)==Q) printf("%d\n",r);
     else printf("impossible\n");
  }
  return 0;
}