问题描述
满足 N! 的末尾恰好有 K 个 0 的最小的 N 是多少?
如果这样的 N 不存在输出 −1。
输入格式
一个整数 K。
输出格式
一个整数代表答案。
样例输入
2
样例输出
10
评测用例规模与约定
对于 30% 的数据,1 ≤ K ≤ 10的6次方
对于 100% 的数据,1 ≤ K ≤ 10的18次方
知识点:数学找规律,二分
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10010;
ll check(ll n)//检查n!后面有几个0
{
ll cnt=0;
while(n)
{
cnt+=n/5;
n/=5;
}
return cnt;
}
int main()
{
ll k;
cin>>k;
ll l=0,r=1e19;//注意l可以从0开始,而不是1
while(l<r)
{
ll mid=l+r>>1;
if(check(mid)>=k)
{
r=mid;
}
else l=mid+1;
}
if(check(l)!=k)
{
cout<<-1<<endl;
}
else cout<<l<<endl;
return 0;
}
通过数学上的找规律,可以找到n!后面0的数量增加的规律,即遇到 n*pow(5,i) 就加上 i 。比如,遇到5,10,15,20,零的数量就加一,遇到25,50,75,零的数量就加二。
如果觉得规律不太好找,也可以用Python先遍历一遍,进行大数据模拟,寻找规律。
n = 30
x = 1
for i in range(1, n + 1):
x *= i
print(i,x)
然后进行二分。因为是寻找恰好有K个0的首位置,所以使用第一种二分方法(如果是末位置则使用第二种模板),模板如下所示:
int bsearch_1(int l,int r,int x)
{
while(l<r)
{
int mid=l+r>>1;
if(a[mid]>=x)
{
r=mid;
}
else l=mid+1;
}
return l;
}