蓝桥杯刷题 二分-[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开始,而不是1
  while(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 *= i
    print(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;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/533011.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

云手机解决海外社媒运营的诸多挑战

随着海外社交媒体运营的兴起&#xff0c;如何有效管理多个账户成为了一项挑战。云手机作为一种新兴的解决方案&#xff0c;为海外社媒运营带来了前所未有的便利。 云手机的基本原理是基于云计算和虚拟化技术&#xff0c;允许用户在物理手机之外创建和使用多个虚拟手机。这种创新…

嵌入式学习52-ARM1

知识零散&#xff1a; 1.flash&#xff1a; nor flash 可被寻地址 …

SOCKS代理概述

在网络技术的广阔领域中&#x1f310;&#xff0c;SOCKS代理是一个核心组件&#xff0c;它在提升在线隐私保护&#x1f6e1;️、实现匿名通信&#x1f3ad;以及突破网络访问限制&#x1f6ab;方面发挥着至关重要的作用。本文旨在深入探讨SOCKS代理的基础&#xff0c;包括其定义…

FPGA - 以太网UDP通信(一)

一&#xff0c;简述以太网 以太网简介 ​以太网是一种计算机局域网技术。IEEE组织的IEEE 802.3标准制定了以太网的技术标准&#xff0c;它规定了包括物理层的连线、电子信号和介质访问层协议的内容。 ​ 以太网类型介绍 以太网是现实世界中最普遍的一种计算机网络。以太网有…

python篇---图片转成视频

python篇—图片转成视频 import cv2 import os# 设置图片文件夹路径和视频输出路径 image_folder /workspace/11 video_name output_video.mp4# 获取图片文件夹中的所有图片文件名&#xff0c;并按顺序排序 images [img for img in os.listdir(image_folder) if img.endswi…

SSH穿透ECS访问内网RDS数据库

处于安全考虑&#xff0c;RDS一般只会允许指定的IP进行访问&#xff0c;而我们开发环境的IP往往是动态的&#xff0c;每次IP变动都需要去修改RDS的白名单&#xff0c;为我们的工作带来很大的不便。 那么如何去解决这个问题&#xff1f; 假如我们有一台ESC服务器&#xff0c;E…

虹科Pico汽车示波器 | 免拆诊断案例 | 2011款东风悦达起亚K5车发动机偶尔起动困难

一、故障现象 一辆2011款东风悦达起亚K5车&#xff0c;搭载G4KD发动机&#xff0c;累计行驶里程约为24.5万km。车主反映&#xff0c;第1次起动发动机时偶尔无法起动着机&#xff0c;第2次能够正常起动着机&#xff0c;但发动机故障灯异常点亮。为此在其他维修厂维修过&#xf…

java Web课程管理系统用eclipse定制开发mysql数据库BS模式java编程jdbc

一、源码特点 JSP 课程管理系统是一套完善的web设计系统&#xff0c;对理解JSP java 编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为TOMCAT7.0,eclipse开发&#xff0c;数据库为Mysql5.0&#xff0c;使用ja…

【PDF.js】PDF文件预览

【PDF.js】PDF文件预览 一、PDF.js二、PDF.js 下载1、下载PDF.js2、在项目中引入3、屏蔽跨域错误 三、项目中使用四、说明五、实现效果 使用PDFJS实现pdf文件的预览&#xff0c;支持预览指定页、关键词搜索、缩略图、页面尺寸调整等等。 一、PDF.js 官方地址 文档地址 二、PD…

SpringCloudAlibaba-整合sleuth和zipkin(六)

目录地址&#xff1a; SpringCloudAlibaba整合-CSDN博客 一、整合sleuth 1.引入依赖 在需要追踪的微服务中引入依赖&#xff0c;user、order、product <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter…

spring boot 集成 flyway依赖 做数据库迁移,让部署没烦恼

flyway 是一个敏捷工具&#xff0c;用于数据库的移植。采用 Java 开发&#xff0c;支持所有兼容 JDBC 的数据库。 主要用于在你的应用版本不断升级的同时&#xff0c;升级你的数据库结构和里面的数据。 还是直接上代码 第一步&#xff1a; <!-- Flyway 数据库迁移 依赖 他…

LeetCode第22题:生成括号【22/1000 python 递归|动态规划】

作者介绍&#xff1a;10年大厂数据\经营分析经验&#xff0c;现任大厂数据部门负责人。 会一些的技术&#xff1a;数据分析、算法、SQL、大数据相关、python 欢迎加入社区&#xff1a;码上找工作http://t.csdnimg.cn/Q59WX作者专栏每日更新&#xff1a; LeetCode解锁1000题: 打…

【I/O】基于事件驱动的 I/O 模型---Reactor

Reactor 模型 BIO 到 I/O 多路复用 为每个连接都创建一个线程 假设我们现在有一个服务器&#xff0c;想要对接多个客户端&#xff0c;那么最简单的方法就是服务端为每个连接都创建一个线程&#xff0c;处理完业务逻辑后&#xff0c;随着连接关闭线程也要销毁&#xff0c;但是…

Meta的新AI深度伪造策略:增加标签,减少下架

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

【MYSQL锁】透彻地理解MYSQL锁

&#x1f525;作者主页&#xff1a;小林同学的学习笔录 &#x1f525;mysql专栏&#xff1a;小林同学的专栏 目录 1.锁 1.1 概述 1.2 全局锁 1.2.1 语法 1.2.1.1 加全局锁 1.2.1.2 数据备份 1.2.1.3 释放锁 1.2.1.4 特点 1.2.1.5 演示 1.3 表级锁 1.3.1 介绍 …

spring-cloud微服务openfeign

Spring Cloud openfeign对Feign进行了增强&#xff0c;使其支持Spring MVC注解&#xff0c;另外还整合了Ribbon和Nacos&#xff0c;从而使得Feign的使用更加方便 优势&#xff0c;openfeign可以做到使用HTTP请求远程服务时就像洞用本地方法一样的体验&#xff0c;开发者完全感…

计算机视觉 | 基于 ORB 特征检测器和描述符的全景图像拼接算法

Hi&#xff0c;大家好&#xff0c;我是半亩花海。本项目实现了基于 ORB 特征检测器和描述符的全景图像拼接算法&#xff0c;能够将两张部分重叠的图像拼接成一张无缝连接的全景图像。 文章目录 一、随机抽样一致算法二、功能实现三、代码解析四、效果展示五、完整代码 一、随机…

如何合理利用Vue 3中的ref和reactive

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

uni-app实现分页--(1)准备工作,首页下拉触底加载更多

实现流程如下: 分析&#xff1a;需要在滚动容器中添加滚动触底&#xff0c;在猜你喜欢中获取数据。难点&#xff1a;如何在父页面调用子组件内的方法。父组件中用ref&#xff0c;并定义组件实例类型&#xff0c;子组件中暴露方法 具体代码如下&#xff1a; 1.在父组件中添加…

去中心化社交媒体:分析 Facebook 在区块链平台上的角色

在当今数字时代&#xff0c;社交媒体已经成为人们日常生活中不可或缺的一部分。然而&#xff0c;随着人们对数据隐私和信息控制的关注不断增加&#xff0c;传统的中心化社交媒体平台也面临着越来越多的质疑和挑战。为了应对这些挑战&#xff0c;越来越多的人开始探索去中心化社…