【蓝桥杯每日一题】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 公约数
题目来源: 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 (…...
【MySQL学习】MySQL的慢查询日志和错误日志
꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN …...
# C++之functional库用法整理
C之functional库用法整理 注:整理一些突然学到的C知识,随时mark一下 例如:忘记的关键字用法,新关键字,新数据结构 C 的function库用法整理 C之functional库用法整理一、functional库的内建仿函数1. 存储和调用函数2. 存…...
查看MySQL版本的方式
文章目录 一、使用cmd输入命令行查看二、在mysql客户端服务器里查询 一、使用cmd输入命令行查看 1、打开 cmd ,输入命令行: mysql --version 2、还是打开cmd,输入命令行:mysql -V (注意了,此时的V是个大写的V) 二、…...
k8s_入门_命令详解
命令详解 kubectl是官方的CLI命令行工具,用于与 apiserver进行通信,将用户在命令行输入的命令,组织并转化为 apiserver能识别的信息,进而实现管理k8s各种资源的一种有效途径 1. 帮助 2. 查看版本信息 3. 查看资源对象等 查看No…...
腾讯、阿里、字节….等大厂都更喜欢什么样的简历?
我985毕业,为什么筛选简历时输给了一个普通一本? 我投了20份简历,为什么没有一个大厂回我? 每次HR收到简历就没下文了,是我的简历有问题吗? 诚然,在求职时,简历往往就是我们给予H…...
OpenHarmony实战:帆移植案例(中)
OpenHarmony实战:帆移植案例(上) Audio服务介绍 服务节点 基于ADM框架的audio驱动对HDI层提供三个服务hdf_audio_render、hdf_audio_capture、hdf_audio_control。 开发板audio驱动服务节点如下: console:/dev # ls -al hdf_au…...
武汉星起航:创始人张振邦智慧领航,孵化伙伴共绘跨境新蓝图!
在风起云涌的跨境电商行业中,武汉星起航电子商务有限公司如同一颗璀璨的明星,引领着众多创业者迈向成功的彼岸。而这一切的背后,都离不开公司创始人张振邦先生的卓越领导与深厚经验。他凭借着在电子商务行业多年的深耕与积累,为武…...
上下收缩、折叠面板
效果: 上下收缩、折叠面板,类似QQ好友列表那种。原理就是在一个布局中,通过button来实现一个独立widget的visible/disable 实现: 1.分组按钮 #ifndef EXPANDPANEL_H #define EXPANDPANEL_H#include <QWidget>class…...
XC7A35T-2FGG484 嵌入式FPGA现场可编程门阵列 Xilinx
XC7A35T-2FGG484 是一款由Xilinx(赛灵思)制造的FPGA(现场可编程门阵列)芯片 以下是XC7A35T-2FGG484 的主要参数: 1. 系列:Artix-7 2. 逻辑单元数量:33280个 3. 工艺技术:28nm 4. …...
淘宝订单API接口:电商业务自动化的新选择
淘宝订单API接口在电商业务自动化中扮演了至关重要的角色。首先,通过API接口,商家可以自动化地查询、创建、修改和删除订单,极大地提高了订单处理效率,减少了人工操作,降低了错误率。其次,商家可以实时获取…...
识典百科词条创建技巧,教你如何轻松创建热门识典百科词条!
网络已经成为人们获取知识和信息的主要途径。在这样一个背景下,识典百科作为一个综合性的网络百科全书,在为读者们提供各种知识的同时,也给广大用户提供了一个创建、编辑和分享知识的平台。如何在识典百科上创建一个高质量的词条,…...
iOS 开发中上传 IPA 文件的方法(无需 Mac 电脑)
引言 在 iOS 开发中,将 IPA 文件上传到苹果开发者中心是一个重要的步骤。通常情况下,我们需要使用 Mac 电脑上的 Xcode 或 Application Loader 工具来完成这个任务。然而,如果你没有 Mac 电脑,也没有关系,本文将介绍一…...
2024-04-08 问AI: 介绍一下AI 大神 吴恩达
文心一言 吴恩达(Andrew Ng)是AI领域的一位重要人物,他的贡献和影响力在学术界、工业界以及在线教育领域都极为显著。 吴恩达出生于1976年,是一位华裔美国人,他在斯坦福大学担任计算机科学系和电子工程系的副教授&am…...
Leetcode面试经典150_Q12整数转罗马数字
题目: 罗马数字包含以下七种字符: I, V, X, L,C,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(Java Native Interfa…...
裙边挡边带是什么
裙边挡边带:了解其功能与应用 在日常生活和工业生产中,我们经常会遇到各种形状和功能的带子。其中,裙边挡边带是一种特殊类型的带子,它具有独特的结构和功能,被广泛应用于各种场合。本文将介绍裙边挡边带的基本概念、…...
chabot项目介绍
项目介绍 整体的目录如下所示: 上述的项目结构中出了model是必须的外,其他的都可以根据训练的代码参数传入进行调整,有些不需要一定存在data train.pkl:对原始训练语料进行tokenize之后的文件,存储一个list对象,list的每条数据表…...
【Python原生AOT编译终极指南】:2026年CPython 3.15+官方AOT源码级拆解与生产落地避坑清单
第一章:Python原生AOT编译的演进脉络与3.15官方定位Python长期以来以解释执行和字节码(.pyc)为默认运行范式,AOT(Ahead-of-Time)编译长期处于社区实验阶段。从Nuitka、Cython到PyO3/Rust绑定,再…...
【原创改进代码】考虑电动汽车移动储能特性的多区域电网功率波动平抑优化调控附python代码
✅作者简介:热爱科研的Matlab仿真开发者,擅长毕业设计辅导、数学建模、数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。 🍎 往期回顾关注个人主页:Matlab科研工作室 👇 关注我领取海量matlab电子…...
无代码自动化:OpenClaw+Qwen3.5-9B可视化流程搭建
无代码自动化:OpenClawQwen3.5-9B可视化流程搭建 1. 为什么选择OpenClawQwen3.5-9B组合 去年夏天,我发现自己每周要花3小时重复做三件事:整理会议录音、提取待办事项、设置日历提醒。当我尝试用传统自动化工具时,要么需要写代码…...
从YOLOv8到RTDETR:如何将训练后的YOLO指标无缝转换为COCO格式
1. 为什么需要YOLO到COCO格式转换 当你用YOLOv8官方代码训练RTDETR模型时,会发现评估结果默认输出的是YOLO格式指标。但学术界和工业界普遍采用COCO评估标准,这就好比在中国用人民币交易,到了欧洲就得换成欧元。我在去年帮某无人机公司做目标…...
BilibiliDown:如何高效批量下载B站视频并实现离线收藏管理?
BilibiliDown:如何高效批量下载B站视频并实现离线收藏管理? 【免费下载链接】BilibiliDown (GUI-多平台支持) B站 哔哩哔哩 视频下载器。支持稍后再看、收藏夹、UP主视频批量下载|Bilibili Video Downloader 😳 项目地址: https://gitcode.…...
TimeGAN实战:用对抗网络生成高保真时间序列数据
1. TimeGAN:当时间序列遇上生成对抗网络 第一次听说TimeGAN这个概念时,我正在处理一批金融交易数据。客户要求我们开发一个高频交易预测模型,但原始数据涉及商业机密,能拿到的样本量只有正常需求的1/10。当时试过传统的数据增强方…...
mysql技巧(十六):覆盖索引 vs 回表 —— 让查询效率提升 10 倍的核心技巧
📝 本章学习目标本章聚焦数据库性能优化,帮助读者彻底掌握覆盖索引与回表的核心原理。通过本章学习,你将全面理解覆盖索引 vs 回表这一核心主题,并能在实际工作中应用这些技巧,让查询效率提升 10 倍以上。 一、引言&am…...
告别重复编码:用快马AI自动生成软件库e7c9的高效调用代码
作为一名经常和第三方库打交道的开发者,我深刻体会到手动编写调用代码的繁琐。尤其是像e7c9这样功能强大的软件库,虽然封装完善,但每次调用都需要反复查阅文档、处理边界情况,效率实在不高。最近尝试用InsCode(快马)平台的AI辅助生…...
保姆级教程:用Python复现MIT Cheetah的刚体模型与正运动学(附代码)
从零实现MIT Cheetah四足机器人刚体建模与运动学仿真 四足机器人一直是机器人领域的热门研究方向,而MIT Cheetah作为开源四足机器人中的佼佼者,其设计理念和算法实现值得每一位机器人爱好者深入研究。本文将带你从零开始,用Python完整实现MI…...
HS2-HF Patch:驱动创作自由的智能补丁系统与需求动态匹配技术
HS2-HF Patch:驱动创作自由的智能补丁系统与需求动态匹配技术 【免费下载链接】HS2-HF_Patch Automatically translate, uncensor and update HoneySelect2! 项目地址: https://gitcode.com/gh_mirrors/hs/HS2-HF_Patch 在游戏创作领域,玩家对个性…...
