蓝桥杯-求阶乘-python

news/2025/2/18 23:02:28/

 问题描述

满足N!的末尾恰好有K个0的最小的N是多少?
如果这样的N不存在输出一1。

思路解析

末尾的0是由10产生的,而10是由质数2和5产生的

在求阶乘的过程中,只要是偶数就会有2,而5相对2更少,所以对于10的数量我们可以用计算5的数量来代替

所以我们的目标就是求1-N中有多少个5

1-5,1-10,1-15,1-20,1-25,分别有1,2,3,4,5+1个5

不难看出,5的个数是最后一个数除以5的商(直至不够除5,因为有些数包括多个5,例如25,包含了两个5)

def five_count(num):count = 0while  !(num%==5) :#商即为5的个数,可以看作是1*5,2*5,3*5... 1,2,3就是包括前面数字中的5的个数的总和count += num//5num = num//5return count

因为要求的N要求最小,即N一定是5的倍数

但是范围太大,即使我们只找5的倍数,还是会超时,

既然是查找,我们便可以利用二分法

l = 1
r = 10**19while(l<r):mid = (l+r)//2ct = five_count(mid)
#一直循环到最接近的结果或符合条件的最终结果if ct < k:l = mid + 1else:r = mid

由于二分循环条件是l<r,(l<=r可能会造成死循环)

所以在最后还要考虑l=r的情况

#当r==l时
if k == five_count(l):print(l)

但是二分法查找的不仅仅是5的倍数,因此我们要考虑非5的倍数

对于非5倍数,我们考虑最接近该数的小于他的5的倍数,换一个说法,即考虑该数除5的商,不考虑余数

我们只需要把循环条件改成num//5即可

def five_count(num):count = 0#不是5的倍数也可以while (num//5):#商即为5的个数,可以看作是1*5,2*5,3*5... 1,2,3就是包括前面数字中的5的个数的总和count += num//5num = num//5return count

完整代码

import os
import sys# 请在此输入您的代码
#计算从1~num中有多少个5,不是5的倍数也可以
def five_count(num):count = 0#不是5的倍数也可以while (num//5):#商即为5的个数,可以看作是1*5,2*5,3*5... 1,2,3就是包括前面数字中的5的个数的总和count += num//5num = num//5return countk = int(input())
l = 1
r = 10**19while(l<r):#mid = l + ((r - l) >> 1)mid = (l+r)//2ct = five_count(mid)#一直循环到最接近的结果或符合条件的最终结果if ct < k:l = mid + 1else:r = mid
#l、r、mid三者最后均相等
#当r==l时
if k == five_count(l):print(l)
else:print(-1)

文章来源:https://blog.csdn.net/m0_64825044/article/details/136001146
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ppmy.cn/news/1345600.html

相关文章

大数据企业应用场景分析

目录 一、企业分析 1.1 企业领域维度分析 1.2 技术服务型维度分析 1.3 细分领域维度分析 二、大数据应用场景 2.1 数据分析 2.2 智能推荐 2.3 产品/流程优化 2.4 异常监测 2.5 智能管理 2.6 人工智能和机器学习 三、总结 前言&#xff1a;想讲清楚大数据应用对企业…

Java学习-常用API(一)

Object类 Object类及其常用方法&#xff1a; 代码示例&#xff1a; Objects Objects类的引入&#xff0c;定义及其常见的方法&#xff1a; 示例 包装类 什么是包装类&#xff1f; 自动装箱和自动拆箱&#xff1a; 常用方法&#xff1a; 注意&#xff1a;字符串的 数值&#xf…

什么是大模型

目录 让你了解什么是大模型什么是大模型&#xff1f;大模型的应用场景常见的大模型技术实例分析&#xff1a;深度学习语言模型GPT-3 让你了解什么是大模型 大模型&#xff08;Big Model&#xff09;是指在机器学习和人工智能领域中处理大规模数据和复杂模型的一种方法或技术。…

web学习笔记(十九)

目录 1.作用域 1.1作用域的概念 1.2作用域的分类 1.2.1全局作用域 1.2.2局部作用域 1.2.3块级作用域&#xff08;ES6新增 &#xff09; 2.变量作用域 2.1全局变量 2.2局部变量 3.作用域链 3.1作用域链的定义 4.垃圾回收机制 4.1定义 4.2如何避免内存泄漏 5.预…

C语言探索:选择排序的实现与解读

当我们需要对一组数据进行排序时&#xff0c;选择排序&#xff08;Selection Sort&#xff09;是一种简单但效率较低的排序算法。它的基本思想是每次从未排序的数据中选择最小&#xff08;或最大&#xff09;的元素&#xff0c;然后将其放置在已排序序列的末尾。通过重复这个过…

零代码3D可视化快速开发平台

老子云平台 老子云3D可视化快速开发平台&#xff0c;集云压缩、云烘焙、云存储云展示于一体&#xff0c;使3D模型资源自动输出至移动端PC端、Web端&#xff0c;能在多设备、全平台进行展示和交互&#xff0c;是全球领先、自主可控的自动化3D云引擎。此技术已经在全球申请了专利…

python介绍,安装Cpython解释器,IDE工具pycharm的使用

python介绍 官方的Python解释器本质是基于C语言开发的一个软件&#xff0c;该软件的功能就是读取以py.结尾的文件内容&#xff0c;然后按照Guido定义好的语法和规则去翻译并执行相应的代码。这种C实现的解释器被称为Cpython。 python解释器的种类&#xff1a;Jython IPyth…

Text Mesh Pro图文混排如何对任何图片都能实现

1&#xff09;Text Mesh Pro图文混排如何对任何图片都能实现 2&#xff09;Unity iOS平台的小图占用特别大的内存 3&#xff09;只在编辑器内&#xff0c;纹理不开启Read&Write情况下&#xff0c;如何获取纹理所有颜色值 4&#xff09;准备在海外发行游戏&#xff0c;有哪些…