当前位置: 首页 > 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的每条数据表…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...