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

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...