题目大意:给你t个输入,每个输入给你一个数N,问你最小一个数的阶乘末尾的0有n的数字是多少,比如5!=120末尾有一个0,不存在这种数字输出impossible
思路:当时校队比赛做的题目,还是太菜做了三小时没做明白,不过结束后听师兄说二分回去花17分钟就做出来了。
首先,要明白一个数每有1个5就会有一个0
可以这么思考:5的阶乘为12345,每有一个5,前面都有偶数和它对应形成10
所以一个数除以5就说明了这个数最少有几个0
但是还有没有特殊情况呢?
有的,比如25的阶乘,最后的一个数25是5*5的乘积,那么前面有两个偶数和它对应,这时候就会多出来一个5
所以25的阶乘末尾0有6个
那么如果你知道一个数的阶乘末尾0的计算方法就出来了
直接把这个数一直除以5,把除以5的数量全部加起来就是末尾0的答案了(全部都是乘除答案)
可惜这题是反过来求数的阶乘
这时候就要利用二分进行快速查找求解了
因为前面全部都是整除的
反推很难找到方法(反正我是想了3小时找不到方法)
那么代码就出来啦
代码:
#include
#include
using namespace std;
int solve(int x){
int cnt=0;
x*=5;
while(x){//求末尾有多少个0,看答案*5的结果对不对
x/=5;
cnt+=x;
}
return cnt;
}
int main()
{
int t;
cin>>t;
int i=1;
while(t--){
int n;
cin>>n;
int l=0,r=n;
int mid;
while(l<=r){//二分
mid=(l+r)/2;
if(solve(mid)<n){
l=mid+1;
}else {
if(solve(mid)==n)break;//通过这个判断是不是impossible
else r=mid-1;
}
}
printf("Case %d: ",i++);
if(solve(mid)==n)cout<<mid*5<<endl;
else cout<<"impossible"<<endl;
}
return 0;
}
京公网安备 11010502036488号