【求阶乘——二分+阶乘的质因数分解】

题目

思路

• 求末尾0的个数转为求5的个数
  • 末尾0的个数依赖于因子10的个数
  • 因子10的个数依赖于因子（2*5）的个数
  • 因子2远多于因子5
  • 最终转化为因子5的个数
• 阶乘的某一因子的个数求解，见：对n质因数分解和对n!质因数分解-CSDN博客
• 答案一定小于等于 5 * k，品品
• 答案区间具有二段性，可以二分
• 最后的答案要求的不是二段性当中的任何一个性质，而是刚好相等！！

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll get(ll x)
{ll retv = 0;while(x){retv += x / 5;x /= 5;}return retv;
}
int main()
{ll k;cin >> k;ll l = 0, r = 5*k;while(l < r){ll mid = l + r >> 1;if(get(mid) >= k) r = mid;else l = mid+1;}if(get(l) != k) l = -1;cout << l;
}