当前位置: 首页 > news >正文

蓝桥杯上岸每日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

http://www.lryc.cn/news/105511.html

相关文章:

  • Codeforces Round 889 (Div. 2)(视频讲解A——D)
  • K8s安全配置:CIS基准与kube-bench工具
  • linux安装python和部署Django项目
  • 00-Hadoop入门
  • SE-Net注意力机制详解
  • 商城免费搭建之java商城 开源java电子商务Spring Cloud+Spring Boot+mybatis+MQ+VR全景+b2b2c bbc
  • 推理加速 --- torch.compile
  • JS-----数据结构与算法(2)
  • 手把手安装TomCat;并部署JPress
  • tensorflow1.13分布式训练 参考资料 -教程原理
  • DP学习第五篇之礼物的最大价值
  • cURL error 1: Protocol “https“ not supported or disabled in libcurl
  • XCode升级后QT无法编译的问题
  • springboot编写mp4视频播放接口
  • 华为OD机试真题 JavaScript 实现【机器人活动区域】【2023Q1 200分】,附详细解题思路
  • C++中的静态分配和动态分配
  • 【Android常见问题(五)】- Flutter项目性能优化
  • JSON转换:实体类和JSONObject互转,List和JSONArray互转(fastjson版)
  • Java单例模式几种代码详解
  • PHP代码审计--理论
  • 在云服务器上,clone github时报Connection timed outexit code: 128
  • 小型双轮差速底盘寻迹功能的实现
  • 第七篇:k8s集群使用helm3安装Prometheus Operator
  • Chrome 75不支持保存成mhtml的解决方法
  • 工程监测振弦采集仪应用于岩土工程监测案例
  • 配置HDFS单机版,打造数据存储的强大解决方案
  • U盘删除的文件怎么找回?4个简单方法分享!
  • 【雕爷学编程】MicroPython动手做(27)——物联网之掌控板小程序2
  • 形参动态内存开辟和柔性数组
  • 【LLM系列之指令微调】长话短说大模型指令微调的“Prompt”