*lightoj 1138 Trailing Zeroes (III) | 二分+数学

本文主要是介绍*lightoj 1138 Trailing Zeroes (III) | 二分+数学，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题问了杰神才知道怎么做。

题意：

给你Q，表示N！的结果后面有Q个零，让你求出最小的N为多少。若无法找到则输出impossible

思路：

根据唯一分解定理，一个自然数可以写成质数的幂次方的乘积。例如10 = 2^1 * 5^1

因为是尾部有Q个零，所以N！的结果中5的幂必须等于Q（此时，2的幂肯定比Q大）。

那么我们如果要求一个数的阶乘的结果5的幂次方是多少。

譬如30！的结果中，5的幂究竟是多少，答案是30/5 = 6， 6/5 = 1；结果为7个。其他数值也是这样求，除到最后的数<5为止。可以自己在纸上验证

AC代码：

#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <iostream>
using namespace std;
int q;
long long cot;
bool OK(long long mid)
{cot = 0;while(mid != 0){cot += mid/5;mid /= 5;}if(cot >= q)  return true;return false;
}
int main()
{ios::sync_with_stdio(false);int T, cas = 0;cin>>T;while(T--){long long check = 0;cin>>q;long long l = 1, r = 1e10;long long ans = 0;while(l <= r){long long mid = (l+r)/2;if(OK(mid)){check = cot;ans = mid;r = mid-1;}elsel = mid+1;}cout<<"Case "<<++cas<<": ";if(check != q)cout<<"impossible"<<endl;elsecout<<ans<<endl;}return 0;
}

这篇关于*lightoj 1138 Trailing Zeroes (III) | 二分+数学的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---