蓝桥杯上岸每日N题 第六期(求阶乘)！！！

蓝桥杯上岸每日N题第六期 ❗️ ❗️ ❗️

同步收录 👇

蓝桥杯上岸必背！！！(持续更新中~)

大家好 我是寸铁💪

冲刺蓝桥杯省一模板大全来啦 🔥

蓝桥杯4月8号就要开始了 🙏

距离蓝桥杯省赛倒数第3天 ❗️ ❗️ ❗️

还没背熟模板的伙伴们背起来 💪 💪 💪

真题千千万万遍，蓝桥省一自然现！ ✌️

日更3000里，蓝桥眷顾你 🌟

暴力出奇迹，打表过样例 👊

祝大家4月8号蓝桥杯上岸 ☀️

不清楚蓝桥杯考什么的点点下方👇

考点秘籍

想背纯享模版的伙伴们点点下方👇

蓝桥杯省一你一定不能错过的模板大全(第一期)

蓝桥杯省一你一定不能错过的模板大全（第二期）

蓝桥杯省一你一定不能错过的模板大全（第三期）

蓝桥杯省一你一定不能错过的模板大全（第四期）！！！

想背注释模版的伙伴们点点下方👇

蓝桥杯必背第一期

蓝桥杯必背第二期

往期精彩回顾

蓝桥杯上岸每日N题 第一期(一)！！！

蓝桥杯上岸每日N题第一期(二)！！！

蓝桥杯上岸每日N题第一期(三)！！！

蓝桥杯上岸每日N题第二期(一)！！！

蓝桥杯上岸每日N题第三期(一)！！！

蓝桥杯上岸每日N题 第四期(最少刷题数)！！！

蓝桥杯上岸每日N题 第五期(山)！！！

操作系统期末题库 第九期(完结)

LeetCode Hot100 刷题(第三期)

idea创建SpringBoot项目报错解决方案

数据库SQL语句（期末冲刺）

想看JavaB组填空题的伙伴们点点下方 👇

填空题

竞赛干货

算法竞赛字符串常用操作大全

蓝桥杯上岸必刷！！！(模拟/枚举专题)

蓝桥杯上岸必背！！！ (第三期 DP)

蓝桥杯上岸必背！！！(第四期DFS)

蓝桥杯上岸必背！！！(第五期BFS)

蓝桥杯上岸必背！！！(第六期树与图的遍历)

蓝桥杯上岸必背！！！(第七期 最短路算法)

蓝桥杯上岸必背！！！(第八期 简单数论)

---

前言

蓝桥杯后天就要开始啦~还没刷题的同学跟我一起来刷历年真题，迟点出考前鲤鱼锦囊 🙏

喜欢的小伙伴可以关注我，关注寸铁，我们一起上岸4.8蓝桥杯！！！

求阶乘

考点：二分+反复整除法

分析

题目问我们的是满足N!的末尾恰好有K个0的最小的N是多少?

思路

阶乘数要想凑出来0必定是有若干个2、5
由于是阶乘2的个数必定是多于5的个数。
因此我们需要去枚举5的个数
没有思路怎么办？

暴力出奇迹，模拟过样例！

10！

10*9*8*7*6*5*4*3*2*1

10、5 总共是2个5
10/5=2

16！

16*15*14*...*10*...*5*...*1

15、10、5总共是3个5
16/5=3
25！

25*...*20*...*15*...*10*...*5

25、20、15、10、5总共有6个5
为什么是6个？
原因在于25可以被拆成5*5，总共是6个5。
所以我们需要反复整除5，这样才能把边界值含5的个数全部统计出来。
最后加上5的个数即可
25/5=5+5/5=6
又如125=5*5*5一共是3个5等于**125/5**
又如625=5*5*5*5一共是**4个5等于625/5**

我们通过模拟可以发现：
我们直接对枚举到的数字整除5判断
输出能整除5是k的数字即可

但是看到k的上界为1e18直接枚举必定**TLE**
题目要求满足N!的末尾恰好有K个0的最小的N
我们需要优化解决,当前N！恰好有k个0。
比N大的N!必定大于K个0,比N小的N！必定小于K个0。

我们直接想到二分来做这道题！！！

怎么二分？

不像最少刷题数那样,满足条件才能进行二分。
这道题直接枚举数字套模板进行二分即可。
因为题目问我们的是最少满足k个0的数字N是多少
不过最后还要检验一下二分出的答案是不是k个0

此外，这题需要考虑一些数据的细节

时间关系,具体看这两个大佬写的博客，写得很棒%%%
博客1
博客2

ACcode

import java.util.*;
public class Main{public static void main(String []args) {Scanner sc=new Scanner(System.in);long k=sc.nextLong();long l=1,r=(long)9e18;//数据要开大//二分while(l<r) {long mid=l+(r-l)/2;//需要再减去l//当前的N拆分成5的倍数的个数大于等于k//说明需要缩减范围,即r=midif(query(mid)>=k)r=mid;//说明不够k需要继续寻找else l=mid+1;}long x=query(r);//再查一下N是不是能被拆成k个5//可以的话输出r//不可以则输出-1if(x==k)System.out.println(r);else System.out.println("-1");}static long query(long x) {long ans=0;//统计能拆分成5的个数while(x>0) {ans+=x/5;//直接让其除以5x/=5;}return ans;}
}

提炼

反复整除法：得出某个数的阶乘含a的个数

	static long query(long x) {long ans=0;//统计能拆分成a的个数while(x>0) {ans+=x/a;//直接让其除以ax/=a;//再对边界x进行反复整除//统计出x还能拆成多少个5/包含多少个5}return ans;}

ACcode2

import java.util.*;
public class Main{public static void main(String []args){Scanner sc=new Scanner(System.in);long k=sc.nextLong();long l=1;long r=(long)9e18;while(l<r){long mid=l+r>>1;if(check(mid)>=k)r=mid;else l=mid+1;}long x=check(r);if(x==k)System.out.println(r);else System.out.println("-1");}public static long check(long x){long ans=0;while(x>0){ans+=x/5;x/=5;}return ans; }
}

参考资源

http://t.csdn.cn/2WxI4
https://blog.csdn.net/weixin_57943259/article/details/124206177