河南省多校连萌（五） Problem C: 不是防AK题

                                               Problem C: 不是防AK题
                          Time Limit: 1 Sec  Memory Limit: 64 MB
                                                                                                 Submit: 271  Solved: 62

SubmitWeb Board
Description
每一个数都有若干个后缀零，比如100有2个、10有1个、1有0个，那么问题来了，已知整数n，求x使其满足x!的后缀零个数为n

Input
输入一个数T (≤ 10000)，表示有T组数据
接下来T行每一行有一个数n (1 ≤ n≤10^8)

Output
每组数据首先输出当前组数（格式参见Sample Output），之后输出满足情况时最小的x，如果x不存在，输出no

Sample Input
3
1
2
5
Sample Output
Case 1: 5
Case 2: 10
Case 3: no
HINT

题意：》》》》

思路：和51nod的一级算法题中的一道题类似，再说一下结论：阶乘后缀0的个数后5的倍数个数有关即：x+=n/5,n/=5

这样我们编写一个小函数算出后缀0的个数，二分答案即可：

下面附上代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int M=1e12+10;
typedef long long ll;
ll solve(ll n)
{
	ll sum=0;
	while(n)
	{
		sum+=n/5;
		n/=5;
	}
	return sum;
} 
int main()
{
	int T,k=0;
	ll x;
	cin>>T;
	while(T--)
	{
		ll ans=0;
		cin>>x;
		ll l=1,r=M;
		while(l<=r)
		{
			ll mid=(l+r)>>1;
			if(solve(mid)==x)
			{
				ans=mid;
				r=mid-1;
			}
			else if(solve(mid)>x)
				r=mid-1;
			else l=mid+1;
		}
		if(ans)
			printf("Case %d: %d\n",++k,ans);
		else
			printf("Case %d: no\n",++k);
	}
	return 0;
}