2145. 求阶乘

求阶乘

满足$N！$的末尾恰好有$K$个$0$的最小的$N$是多少?
如果这样的$N$不存在输出$-1$。
输入格式：一个整数$K$。
输出格式：一个整数代表答案。

样例

---

Example

样例输入
2

样例输出
10

评测用例规模与约定
对于30%的数据，1 ≤ K ≤ 10^6
对于100%的数据，1 ≤ K ≤ 10

思路

---

求$N！$的末尾0的个数可以用勒让德公式计算5的最高幂指数，又因为末尾0的个数随着$N！$的增加具有单调性，因此使用二分答案进行求解。

答案

---

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll k;
ll ans;
 
ll count(ll n, ll p)
{
  ll res = 0;
  while(n > 0)
  {
    res += n / p;
    n /= p;
  }
  return res;
}
 
int main()
{
  cin >> k;
  ll l = 0, r = 1e20;
  while(l <= r)
  {
    ll mid = (l + r) / 2;
    ll cnt = count(mid, 5);
    if(cnt == k)
    {
      ans = mid;
      r = mid - 1;
    } 
    else if(cnt > k)
      r = mid - 1;
    else 
      l = mid + 1;
  }
  if(ans == 0)
    cout << -1;
  else 
    cout << ans;
  return 0;
}