题目大意:给你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; }