数论 + 二分 (阶乘后缀0的个数) - Trailing Zeroes (III) - LightOJ 1138

数论 + 二分 (阶乘后缀0的个数) - Trailing Zeroes (III) - LightOJ 1138

题意：

$n的阶乘尾部有q个连续的0，现在给你q，请你算出满足条件的n，如果有多个n满足条件，输出最小的那个即可。$

Input

输入一个T(T ≤ 10000),表示样例数量。

每个样例输入一个q。(1 ≤ q ≤ 100,000,000)

Output

对于每个样例，输出满足条件的最小的n，如果没有满足条件的则输出"impossible"。

Sample Input

3
1
2
5

Sample Output

Case 1: 5
Case 2: 10
Case 3: impossible

$Time\ limit:2000 ms,Memory \ limit:32768 kB$

分析：

$每个数的后缀0的个数，取决于其质因子2和5的指数。$

$阶乘后缀0的个数，取决于质因子5的指数，因为5的指数恒大于等于2的指数。$

$因为答案是满足单调性的，求最小值，我们可以直接二分答案。$

$对每个二分的答案mid，我们判断mid的阶乘，质因子5的指数,cal(mid)是否大于等于q。$

$二分得到满足mid!的因子5的指数,cal(mid)≥q的最小的mid，$

$然后我们看cal(mid)=q是否成立即可。$

注意：

$二分的边界l=5，考虑右边界r：$

$至多有10^9个后缀0，即因子5的指数为10^9，$

$每间隔10，至少会出现两个数的因子中包含5^1，$

$则\frac{r}{10}×2=10^9，可得r=5×10^9，可粗略估计出右边界不超过5×10^9。$

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>#define ll long longusing namespace std;ll cal(ll n)
{ll s=0;for(ll i=n;i;i/=5) s+=i/5;return s;
}int main()
{int T; cin>>T;for(int t=1;t<=T;t++){int q; scanf("%d",&q);ll l=5, r=1e10;while(l<r){ll mid=l+r>>1;if(cal(mid)>=q) r=mid;else l=mid+1;}printf("Case %d: ",t);if(cal(l)!=q) puts("impossible");else printf("%lld\n",l);}return 0;
}