蓝桥杯刷题 二分-[2145]求阶乘（C++）

本文主要是介绍蓝桥杯刷题 二分-[2145]求阶乘（C++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

满足 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开始，而不是1while(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 *= iprint(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;
}

这篇关于蓝桥杯刷题 二分-[2145]求阶乘（C++）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---