给一个整数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;
}