上上佳食品 网站建设,采购需求网站建设,百度高级搜索技巧,网站设计公司网站制作费用蓝桥杯上岸每日N题第六期 ❗️ ❗️ ❗️
同步收录 #x1f447;
蓝桥杯上岸必背#xff01;#xff01;#xff01;(持续更新中~)
大家好 我是寸铁#x1f4aa;
冲刺蓝桥杯省一模板大全来啦 #x1f525;
蓝桥杯4月8号就要开始了 #x1f64f;
距离蓝桥杯省赛倒数…蓝桥杯上岸每日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*110、5 总共是2个5 10/52
16
16*15*14*...*10*...*5*...*115、10、5总共是3个5 16/53 25
25*...*20*...*15*...*10*...*525、20、15、10、5总共有6个5 为什么是6个 原因在于25可以被拆成5*5总共是6个5。 所以我们需要反复整除5这样才能把边界值含5的个数全部统计出来。 最后加上5的个数即可 25/555/56 又如1255*5*5一共是3个5等于**125/5** 又如6255*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 scnew Scanner(System.in);long ksc.nextLong();long l1,r(long)9e18;//数据要开大//二分while(lr) {long midl(r-l)/2;//需要再减去l//当前的N拆分成5的倍数的个数大于等于k//说明需要缩减范围,即rmidif(query(mid)k)rmid;//说明不够k需要继续寻找else lmid1;}long xquery(r);//再查一下N是不是能被拆成k个5//可以的话输出r//不可以则输出-1if(xk)System.out.println(r);else System.out.println(-1);}static long query(long x) {long ans0;//统计能拆分成5的个数while(x0) {ansx/5;//直接让其除以5x/5;}return ans;}
}
提炼
反复整除法得出某个数的阶乘含a的个数 static long query(long x) {long ans0;//统计能拆分成a的个数while(x0) {ansx/a;//直接让其除以ax/a;//再对边界x进行反复整除//统计出x还能拆成多少个5/包含多少个5}return ans;}ACcode2
import java.util.*;
public class Main{public static void main(String []args){Scanner scnew Scanner(System.in);long ksc.nextLong();long l1;long r(long)9e18;while(lr){long midlr1;if(check(mid)k)rmid;else lmid1;}long xcheck(r);if(xk)System.out.println(r);else System.out.println(-1);}public static long check(long x){long ans0;while(x0){ansx/5;x/5;}return ans; }
}参考资源
http://t.csdn.cn/2WxI4 https://blog.csdn.net/weixin_57943259/article/details/124206177
