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

【蓝桥杯每日一题】4.8 公约数

题目来源:

4199. 公约数 - AcWing题库

问题描述:

​ 找到最大整数x,需满足下面两个条件

  • x x x a a a, b b b的公约数
  • l < = x < = r l<=x<=r l<=x<=r

思路:

  • 找到 a a a, b b b两个数的最大公约数 g c = g c d ( a , b ) gc=gcd(a,b) gc=gcd(a,b)
  • 将此最大公约数的所有约数存放在一个数组 g g g
  • 二分查找该数组 g g g,找到满足条件的值

AC Code:

//gcd+约数分解+二分查找
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10; //x的约数不会超过2*sqrt(x)个ll a,b,q,x,y;
ll g[N];
ll cnt=0;int gcd(ll a,ll b)
{return b?gcd(b,a%b):a;
}void div(ll x)
{for(ll i=1;i<=x/i;i++){if(x%i==0){g[cnt++]=i;if(i!=x/i) g[cnt++] = x/i; //相当于用遍历从1->x的时间 记录了x的所有约数}	}sort(g,g+cnt);
}
int main()
{scanf("%ld%ld",&a,&b);div(gcd(a,b));scanf("%ld",&q);while(q--){scanf("%ld%ld",&x,&y);int l=-1,r=cnt;while(l+1<r){int mid=(l+r)/2;if(g[mid]<=y) l=mid;else r=mid;}if(g[l]>=x) printf("%ld\n",g[l]);else printf("-1\n");}return 0;
}

相关文章:

【蓝桥杯每日一题】4.8 公约数

题目来源&#xff1a; 4199. 公约数 - AcWing题库 问题描述&#xff1a; ​ 找到最大整数x&#xff0c;需满足下面两个条件 x x x是 a a a, b b b的公约数 l < x < r l<x<r l<x<r 思路&#xff1a; 找到 a a a, b b b两个数的最大公约数 g c g c d (…...

【MySQL学习】MySQL的慢查询日志和错误日志

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN …...

# C++之functional库用法整理

C之functional库用法整理 注&#xff1a;整理一些突然学到的C知识&#xff0c;随时mark一下 例如&#xff1a;忘记的关键字用法&#xff0c;新关键字&#xff0c;新数据结构 C 的function库用法整理 C之functional库用法整理一、functional库的内建仿函数1. 存储和调用函数2. 存…...

查看MySQL版本的方式

文章目录 一、使用cmd输入命令行查看二、在mysql客户端服务器里查询 一、使用cmd输入命令行查看 1、打开 cmd &#xff0c;输入命令行&#xff1a; mysql --version 2、还是打开cmd&#xff0c;输入命令行&#xff1a;mysql -V (注意了&#xff0c;此时的V是个大写的V) 二、…...

k8s_入门_命令详解

命令详解 kubectl是官方的CLI命令行工具&#xff0c;用于与 apiserver进行通信&#xff0c;将用户在命令行输入的命令&#xff0c;组织并转化为 apiserver能识别的信息&#xff0c;进而实现管理k8s各种资源的一种有效途径 1. 帮助 2. 查看版本信息 3. 查看资源对象等 查看No…...

腾讯、阿里、字节….等大厂都更喜欢什么样的简历?

我985毕业&#xff0c;为什么筛选简历时输给了一个普通一本&#xff1f; 我投了20份简历&#xff0c;为什么没有一个大厂回我&#xff1f; 每次HR收到简历就没下文了&#xff0c;是我的简历有问题吗&#xff1f; 诚然&#xff0c;在求职时&#xff0c;简历往往就是我们给予H…...

OpenHarmony实战:帆移植案例(中)

OpenHarmony实战&#xff1a;帆移植案例&#xff08;上&#xff09; Audio服务介绍 服务节点 基于ADM框架的audio驱动对HDI层提供三个服务hdf_audio_render、hdf_audio_capture、hdf_audio_control。 开发板audio驱动服务节点如下&#xff1a; console:/dev # ls -al hdf_au…...

武汉星起航:创始人张振邦智慧领航,孵化伙伴共绘跨境新蓝图!

在风起云涌的跨境电商行业中&#xff0c;武汉星起航电子商务有限公司如同一颗璀璨的明星&#xff0c;引领着众多创业者迈向成功的彼岸。而这一切的背后&#xff0c;都离不开公司创始人张振邦先生的卓越领导与深厚经验。他凭借着在电子商务行业多年的深耕与积累&#xff0c;为武…...

上下收缩、折叠面板

效果&#xff1a; 上下收缩、折叠面板&#xff0c;类似QQ好友列表那种。原理就是在一个布局中&#xff0c;通过button来实现一个独立widget的visible/disable 实现&#xff1a; 1.分组按钮 #ifndef EXPANDPANEL_H #define EXPANDPANEL_H#include <QWidget>class…...

XC7A35T-2FGG484 嵌入式FPGA现场可编程门阵列 Xilinx

XC7A35T-2FGG484 是一款由Xilinx&#xff08;赛灵思&#xff09;制造的FPGA&#xff08;现场可编程门阵列&#xff09;芯片 以下是XC7A35T-2FGG484 的主要参数&#xff1a; 1. 系列&#xff1a;Artix-7 2. 逻辑单元数量&#xff1a;33280个 3. 工艺技术&#xff1a;28nm 4. …...

淘宝订单API接口:电商业务自动化的新选择

淘宝订单API接口在电商业务自动化中扮演了至关重要的角色。首先&#xff0c;通过API接口&#xff0c;商家可以自动化地查询、创建、修改和删除订单&#xff0c;极大地提高了订单处理效率&#xff0c;减少了人工操作&#xff0c;降低了错误率。其次&#xff0c;商家可以实时获取…...

识典百科词条创建技巧,教你如何轻松创建热门识典百科词条!

网络已经成为人们获取知识和信息的主要途径。在这样一个背景下&#xff0c;识典百科作为一个综合性的网络百科全书&#xff0c;在为读者们提供各种知识的同时&#xff0c;也给广大用户提供了一个创建、编辑和分享知识的平台。如何在识典百科上创建一个高质量的词条&#xff0c;…...

iOS 开发中上传 IPA 文件的方法(无需 Mac 电脑)

引言 在 iOS 开发中&#xff0c;将 IPA 文件上传到苹果开发者中心是一个重要的步骤。通常情况下&#xff0c;我们需要使用 Mac 电脑上的 Xcode 或 Application Loader 工具来完成这个任务。然而&#xff0c;如果你没有 Mac 电脑&#xff0c;也没有关系&#xff0c;本文将介绍一…...

2024-04-08 问AI: 介绍一下AI 大神 吴恩达

文心一言 吴恩达&#xff08;Andrew Ng&#xff09;是AI领域的一位重要人物&#xff0c;他的贡献和影响力在学术界、工业界以及在线教育领域都极为显著。 吴恩达出生于1976年&#xff0c;是一位华裔美国人&#xff0c;他在斯坦福大学担任计算机科学系和电子工程系的副教授&am…...

Leetcode面试经典150_Q12整数转罗马数字

题目&#xff1a; 罗马数字包含以下七种字符&#xff1a; I&#xff0c; V&#xff0c; X&#xff0c; L&#xff0c;C&#xff0c;D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M …...

Docker-compose部署Alertmanager+Dingtalk+Prometheus+Grafana实现钉钉报警

部署监控 version: 3.7services: #dingtalkdingtalk:image: timonwong/prometheus-webhook-dingtalk:latestcontainer_name: dingtalkrestart: alwayscommand:- --config.file/etc/prometheus-webhook-dingtalk/config.ymlvolumes:- /data/monitor/dingtalk/config.yml:/etc/p…...

算法刷题记录 Day40

算法刷题记录 Day40 Date: 2024.04.06 kamma 56. 多重背包 #include<bits/stdc.h> using namespace std;int main(){int n, c;while(cin>>c>>n){vector<int> weights(n, 0);vector<int> values(n, 0);vector<int> knums(n, 0);for(int …...

Android JNI基础

目录 一、JNI简介1.1 什么是JNI1.2 用途1.3 优点 二、初探JNI2.1 新建cpp\cmake2.2 build.gradle配置2.3 java层配置2.4 cmake和c 三、API详解3.1 JNI API3.1.1 数据类型3.1.2 方法 3.2 CMake脚本 四、再探JNI 一、JNI简介 1.1 什么是JNI JNI&#xff08;Java Native Interfa…...

裙边挡边带是什么

裙边挡边带&#xff1a;了解其功能与应用 在日常生活和工业生产中&#xff0c;我们经常会遇到各种形状和功能的带子。其中&#xff0c;裙边挡边带是一种特殊类型的带子&#xff0c;它具有独特的结构和功能&#xff0c;被广泛应用于各种场合。本文将介绍裙边挡边带的基本概念、…...

chabot项目介绍

项目介绍 整体的目录如下所示&#xff1a; 上述的项目结构中出了model是必须的外&#xff0c;其他的都可以根据训练的代码参数传入进行调整&#xff0c;有些不需要一定存在data train.pkl:对原始训练语料进行tokenize之后的文件,存储一个list对象&#xff0c;list的每条数据表…...

OpenClaw多语言支持:Qwen2.5-VL-7B跨语种图文处理技巧

OpenClaw多语言支持&#xff1a;Qwen2.5-VL-7B跨语种图文处理技巧 1. 为什么需要多语言图文处理 上周我收到一份混合了英文技术文档和中文注释的项目资料&#xff0c;需要整理成统一格式的双语对照版本。手动复制粘贴到翻译工具再调整排版&#xff0c;花了我整整三个小时。这…...

FastAPI + TinyDB并发陷阱与实战:告别数据错乱的解决方案

核心摘要本文针对在FastAPI框架下使用TinyDB&#xff08;JSON文件数据库&#xff09;时遇到的并发写入数据冲突、错乱问题&#xff0c;深入浅出地解释了问题根源&#xff0c;并提供了从“文件锁”到“内存队列”再到“乐观锁”的三种由浅入深的实战解决方案&#xff0c;帮助你根…...

OpenClaw学习助手:Gemma-3-12b-it生成错题本与定制复习计划

OpenClaw学习助手&#xff1a;Gemma-3-12b-it生成错题本与定制复习计划 1. 为什么需要AI学习助手&#xff1f; 作为一名经常需要处理大量学习资料的开发者&#xff0c;我一直在寻找能够提升学习效率的工具。传统的错题本整理方式需要手动抄写题目、标注知识点、寻找同类练习题…...

DOL-CHS-MODS整合包:从新手入门到定制开发的完整指南

DOL-CHS-MODS整合包&#xff1a;从新手入门到定制开发的完整指南 【免费下载链接】DOL-CHS-MODS Degrees of Lewdity 整合 项目地址: https://gitcode.com/gh_mirrors/do/DOL-CHS-MODS 一、需求定位&#xff1a;你属于哪种玩家类型&#xff1f; 场景描述 不同玩家对游…...

基于西门子PLC的空压机组储气风冷机组自动控制系统:“手动自动切换、多机控制及实时监测报警系统

基于西门子plc的空压机组储气风冷机组自动控制系统 可以实现手动自动切换 三组空压机分别自动控制&#xff0c;自动检测三路压力 风冷机运行实时检测 报警查寻&#xff0c;参数设置等上周刚把车间那套跑了快十年的空压机组控制系统给换了&#xff0c;用的是西门子S7-1200&#…...

突破限制的完整方案:开源工具免费解锁Cursor Pro功能实战指南

突破限制的完整方案&#xff1a;开源工具免费解锁Cursor Pro功能实战指南 【免费下载链接】cursor-free-vip [Support 0.45]&#xff08;Multi Language 多语言&#xff09;自动注册 Cursor Ai &#xff0c;自动重置机器ID &#xff0c; 免费升级使用Pro 功能: Youve reached y…...

效率飙升,跳过proteus安装配置,用快马ai秒建仿真项目

最近在做一个温度监测系统的项目&#xff0c;需要验证电路设计的可行性。按照传统方式&#xff0c;我得先下载安装Proteus软件&#xff0c;配置各种库文件&#xff0c;光是环境准备就得折腾半天。不过这次尝试了用InsCode(快马)平台的AI功能&#xff0c;整个过程变得异常高效。…...

DBeaver驱动包终极指南:一键配置30+数据库,彻底告别网络依赖

DBeaver驱动包终极指南&#xff1a;一键配置30数据库&#xff0c;彻底告别网络依赖 【免费下载链接】dbeaver-driver-all dbeaver所有jdbc驱动都在这&#xff0c;dbeaver all jdbc drivers ,come and download with me , one package come with all jdbc drivers. 项目地址: …...

SSM+JSP洪涝灾情应急物资管理系统源码+论文

代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339; 分享万套开题报告任务书答辩PPT模板 作者完整代码目录供你选择&#xff1a; 《SpringBoot网站项目》1800套 《SSM网站项目》1500套 《小程序项目》1600套 《APP项目》1500套 《Python网站项目》…...

工程伦理案例分析:从经典失败项目看责任分配与风险预防

工程伦理案例分析&#xff1a;从经典失败项目看责任分配与风险预防 当一座桥梁在通车典礼上轰然倒塌&#xff0c;当一栋新建大楼在台风中支离破碎&#xff0c;这些触目惊心的工程事故背后&#xff0c;往往隐藏着复杂的伦理困境。工程伦理不是简单的对错判断题&#xff0c;而是需…...