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

蓝桥杯真题 - 公因数匹配 - 题解

题目链接:https://www.lanqiao.cn/problems/3525/learning/

个人评价:难度 2 星(满星:5)
前置知识:调和级数


整体思路

  • 题目描述不严谨,没说在无解的情况下要输出什么(比如 n n n 1 1 1),所以我们先假设数据保证有解;
  • 2 2 2 1 0 6 10^6 106 枚举 x x x 作为约数,对于约数 x x x 去扫所有 x x x 的倍数,总共需要扫 n 2 + n 3 + n 4 + ⋯ + n n ≈ n ln ⁡ n \frac{n}{2}+\frac{n}{3}+\frac{n}{4}+\cdots+\frac{n}{n}\approx n\ln n 2n+3n+4n++nnnlnn 次;
  • 取所有 x x x 的倍数在原数组中的下标,这些下标对应的数字一定同时包含 x x x 这个约数,取这些下标中最小的两个 i d x 1 , i d x 2 idx_1,idx_2 idx1,idx2,就是满足题意的以 x x x 为约数的两个数的下标;
  • 最后对所有约数 x x x 取最满足题意的 i d x 1 , i d x 2 idx_1,idx_2 idx1,idx2 即可(如果存在多组 i , j i,j i,j,请输出 i i i 最小的那组。如果仍然存在多组 i , j i,j i,j,请输出 i i i 最小的所有方案中 j j j 最小的那组。)

过题代码

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int maxn = 1000000 + 100;
int n, x;
pair<int, int> ans;
vector<int> idx[maxn];
priority_queue<int> que;int main() {
#ifdef ExRocfreopen("test.txt", "r", stdin);
#endif // ExRocios::sync_with_stdio(false);cin >> n;ans = {n + 1, n + 1};for (int i = 1; i <= n; ++i) {cin >> x;idx[x].push_back(i);}for (int i = 1; i < maxn; ++i) {sort(idx[i].begin(), idx[i].end());while (idx[i].size() > 2) {idx[i].pop_back();}}for (int i = 2; i < maxn; ++i) {while (!que.empty()) {que.pop();}for (int j = i; j < maxn; j += i) {for (int k = 0; k < idx[j].size(); ++k) {que.push(idx[j][k]);if (que.size() > 2) {que.pop();}}}if (que.size() < 2) {continue;}int r = que.top();que.pop();int l = que.top();que.pop();if (l < ans.first) {ans = {l, r};} else if (l == ans.first) {if (r < ans.second) {ans = {l, r};}}}cout << ans.first << " " << ans.second << endl;return 0;
}

相关文章:

蓝桥杯真题 - 公因数匹配 - 题解

题目链接&#xff1a;https://www.lanqiao.cn/problems/3525/learning/ 个人评价&#xff1a;难度 2 星&#xff08;满星&#xff1a;5&#xff09; 前置知识&#xff1a;调和级数 整体思路 题目描述不严谨&#xff0c;没说在无解的情况下要输出什么&#xff08;比如 n n n …...

Java 8 Stream API

文章目录 Java 8 Stream API1. Stream2. Stream 的创建3. 常见的 Stream 操作3.1 中间操作3.2 终止操作 4. Stream 的并行操作 Java 8 Stream API Java 8 引入了 Stream API&#xff0c;使得对集合类&#xff08;如 List、Set 等&#xff09;的操作变得更加简洁和直观。Stream…...

AI刷题-还原原始字符串、大数和中的极值位距离

目录 一、还原原始字符串 问题描述 举例 输入格式 输出格式 输入 输出 输入 输出 输入 输出 输入 输出 输入 输出 输入 输出 数据范围 解题思路&#xff1a; 数据结构选择 最终代码&#xff1a; 运行结果&#xff1a; 二、大数和中的极值位距离 问题…...

Ubuntu20.04取消root账号自动登录的方法,触觉智能RK3568开发板演示

Ubuntu20.04默认情况下为root账号自动登录&#xff0c;本文介绍如何取消root账号自动登录&#xff0c;改为通过输入账号密码登录&#xff0c;使用触觉智能EVB3568鸿蒙开发板演示&#xff0c;搭载瑞芯微RK3568&#xff0c;四核A55处理器&#xff0c;主频2.0Ghz&#xff0c;1T算力…...

MySQL 数据库 :SQL 语句规约(不得使用外键与级联,一切外键概念必须在应用层解决。)

文章目录 I 强制规约表名限定数据订正禁止使用存储过程,存储过程难以调试和扩展,更没有移植性。不得使用外键与级联,一切外键概念必须在应用层解决。使用 ISNULL() 来判断是否为 NULL 值NPE 问题不要使用 count(列名) 或 count(常量) 来替代 count(*)II 建议in 操作能避免则…...

深入理解 SQL 中的 DATEDIFF 函数

深入理解 SQL 中的 DATEDIFF 函数 DATEDIFF 函数在 SQL 中是一个用于计算两个日期之间差值的重要工具。不同数据库实现了不同版本的 DATEDIFF&#xff0c;它们在功能和语法上有所不同。本文将详细解析 DATEDIFF 的用法、数据库间差异、复杂场景中的应用&#xff0c;以及替代方…...

【Linux】15.Linux进程概念(4)

文章目录 程序地址空间前景回顾C语言空间布局图&#xff1a;代码1代码2代码3代码4代码5代码6代码7 程序地址空间前景回顾 历史核心问题&#xff1a; pid_t id fork(); if(id 0) else if(id>0) 为什么一个id可以放两个值呢&#xff1f;之前没有仔细讲。 C语言空间布局图&am…...

KubeSphere部署安装,接入KubeKey安装的k8s集群

KubeSphere安装接入KubeKey安装的k8s集群 文章目录 KubeSphere安装接入KubeKey安装的k8s集群 一.NFS安装配置1.服务器安装NFS服务2.下载并部署 NFS Subdir External Provisioner1).下载部署文件2).创建 NameSpace3).创建 RBAC 资源4).配置 deployment.yaml5).部署 Storage Clas…...

opencv3.4 ffmpeg3.4 arm-linux 交叉编译

一些依赖安装&#xff1a; sudo apt-get install pkg-config libgtk2.0-dev libavcodec-dev libavformat-dev libswscale-dev 交叉编译工具链准备&#xff1a;gcc-linaro-6.3.1 1、下载 https://github.com/FFmpeg/FFmpeg 解压后新建目录&#xff1a;Fmpeg-n3.4.13/ffmpeg…...

Java基础(二)

提示:这部分内容对逆向重要,需重点掌握。 1.常见数据类型 1.1 List系列 类似于Python中的列表 List是一个接口,接口下面有两个常见的类型(目的是可以存放动态的多个数据) ArrayList,连续的内存地址存储(内部自动扩容) -> Python列表的特点LinkedList,底层基于链表…...

网络IO与IO多路复用

一、网络IO基础 系统对象&#xff1a; 网络IO涉及用户空间调用IO的进程或线程以及内核空间的内核系统。例如&#xff0c;当进行read操作时&#xff0c;会经历两个阶段&#xff1a; 等待数据准备就绪。将数据从内核拷贝到进程或线程中。 多种网络IO模型的出现原因&#xff1a;…...

C# OpenCvSharp 部署3D人脸重建3DDFA-V3

目录 说明 效果 模型信息 landmark.onnx net_recon.onnx net_recon_mbnet.onnx retinaface_resnet50.onnx 项目 代码 下载 参考 C# OpenCvSharp 部署3D人脸重建3DDFA-V3 说明 地址&#xff1a;https://github.com/wang-zidu/3DDFA-V3 3DDFA_V3 uses the geometri…...

【机器学习实战入门】使用OpenCV进行性别和年龄检测

Gender and Age Detection Python 项目 首先,向您介绍用于此高级 Python 项目的性别和年龄检测中的术语: 什么是计算机视觉? 计算机视觉是一门让计算机能够像人类一样观察和识别数字图像和视频的学科。它面临的挑战大多源于对生物视觉有限的了解。计算机视觉涉及获取、处…...

Android SystemUI——StatusBar视图创建(六)

上一篇文章我们介绍了 StatusBar 的构建过程,在 makeStatusBarView() 中获得 FragmentHostManager,用来管理 StatusBar 的窗口。 一、状态栏视图 在得到 FragmentHostManager 实例对象之后,还会继续调用 addTagListener() 方法设置监听对象,然后获取 FragmentManager 并开…...

解决 Error: Invalid or corrupt jarfile day04_studentManager.jar 报错问题

在 Java 开发过程中&#xff0c;我们可能会遇到这样的报错信息&#xff1a;Error: Invalid or corrupt jarfile day04_studentManager.jar。这个错误通常表示 day04_studentManager.jar 文件可能已损坏或无效&#xff0c;下面将为大家详细介绍如何解决这个问题。 一、错误点分…...

《MambaIR:一种基于状态空间模型的简单图像修复基线方法》学习笔记

paper&#xff1a;2402.15648 目录 摘要 一、引言 1、模型性能的提升依赖于网络感受野的扩大&#xff1a; 2、全局感受野和高效计算之间存在固有矛盾&#xff1a; 3、改进版 Mamba的巨大潜力 4、Mamba 在图像修复任务中仍面临以下挑战&#xff1a; 5、方法 6、主要贡献…...

【转】厚植根基,同启新程!一文回顾 2024 OpenHarmony 社区年度工作会议精彩瞬间

在数字化浪潮奔腾不息的今天&#xff0c;开源技术已成为推动科技创新与产业发展的强大引擎。2025年1月10日-11日&#xff0c;OpenAtom OpenHarmony&#xff08;开放原子开源鸿蒙&#xff0c;以下简称“OpenHarmony”或“开源鸿蒙”&#xff09;社区2024年度工作会议于深圳盛大启…...

2024年我的技术成长之路

2024年我的技术成长之路 大家好&#xff0c;我是小寒。又到年底了&#xff0c;一年过得真快啊&#xff01;趁着这次活动的机会&#xff0c;和大家聊聊我这一年在技术上的收获和踩过的坑。 说实话&#xff0c;今年工作特别忙&#xff0c;写博客的时间比去年少了不少。不过还是…...

最长递增子序列问题(Longest Increasing Subsequence),动态规划法解决,贪心算法 + 二分查找优化

问题描述&#xff1a;在一个大小乱序的数列中&#xff0c;找到一个最大长度的递增子序列&#xff0c;子序列中的数据在原始数列中的相对位置保持不变&#xff0c;可以不连续&#xff0c;但必须递增。 输入描述&#xff1a; 第一行输入数列的长度 n。(1 < n < 200) 第二…...

【Idea】编译Spring源码 read timeout 问题

Idea现在是大家工作中用的比较多的开发工具&#xff0c;尤其是做java开发的&#xff0c;那么做java开发&#xff0c;了解spring框架源码是提高自己技能水平的一个方式&#xff0c;所以会从spring 官网下载源码&#xff0c;导入到 Idea 工具并编译&#xff0c;但是发现build的时…...

基于 HTML5 Canvas 制作一个精美的 2048 小游戏--day2

为了使 2048 游戏的设计更加美观和用户友好&#xff0c;我们可以进行以下几项优化&#xff1a; 改善颜色方案&#xff1a;使用更温馨的颜色组合。添加动画效果&#xff1a;为方块的移动和合并添加渐变效果。优化分数显示&#xff1a;在分数增加时使用动画效果。 以下是改进后…...

服务化架构 IM 系统之应用 MQ

在微服务化系统中&#xff0c;存在三个最核心的组件&#xff0c;分别是 RPC、注册中心和MQ。 在前面的两篇文章&#xff08;见《服务化架构 IM 系统之应用 RPC》和《服务化架构 IM 系统之应用注册中心》&#xff09;中&#xff0c;我们站在应用的视角分析了普适性的 RPC 和 注…...

IoTDB 常见问题 QA 第四期

关于 IoTDB 的 Q & A IoTDB Q&A 第四期来啦&#xff01;我们将定期汇总我们将定期汇总社区讨论频繁的问题&#xff0c;并展开进行详细回答&#xff0c;通过积累常见问题“小百科”&#xff0c;方便大家使用 IoTDB。 Q1&#xff1a;Java 中如何使用 SSL 连接 IoTDB 问题…...

Objective-C语言的数据类型

Objective-C数据类型详解 Objective-C是一种面向对象的编程语言&#xff0c;主要用于macOS和iOS应用程序的开发。作为C语言的超集&#xff0c;Objective-C继承了C语言的基本数据类型&#xff0c;同时也引入了一些独特的特性。本文将对Objective-C的各种数据类型进行详细的介绍…...

3d系统误差分析

系统标定重投影误差预估 在计算机视觉和三维重建领域中&#xff0c;评估一个相机系统标定精度的重要指标。通过比较真实的三维点在图像中的投影位置与标定模型计算出的投影位置之间的差异&#xff0c;来衡量标定的准确性。 以下是对这一概念的详细解析&#xff1a; 什么是系统…...

单片机的原理及其应用:从入门到进阶的全方位指南

以下是一篇详细、深入的“单片机的原理及其应用”博客文章示例&#xff0c;适合想要系统学习或深入了解单片机的读者。文中不仅会介绍单片机的基本原理、内部构造、开发流程和应用领域&#xff0c;还会融入更多的理论分析、实操案例以及常见问题与解决思路等&#xff0c;帮助读…...

在.NET用C#将Word文档转换为HTML格式

将Word文档转换为HTML格式尤其具有显著的优势&#xff0c;它不仅能够确保文档内容在多种设备和平台上保持一致灵活的显示&#xff0c;还便于通过网络进行传播和集成到各种Web应用中。随着越来越多的企业和开发者寻求更灵活、更具兼容性的文件处理方式&#xff0c;.NET框架下的C…...

智能学习平台系统设计与实现(代码+数据库+LW)

摘 要 传统办法管理信息首先需要花费的时间比较多&#xff0c;其次数据出错率比较高&#xff0c;而且对错误的数据进行更改也比较困难&#xff0c;最后&#xff0c;检索数据费事费力。因此&#xff0c;在计算机上安装智能学习平台系统软件来发挥其高效地信息处理的作用&#…...

ASP .NET Core 学习(.NET9)配置接口访问路由

新创建的 ASP .NET Core Web API项目中Controller进行请求时&#xff0c;是在地址:端口/Controller名称进行访问的&#xff0c;这个时候Controller的默认路由配置如下 访问接口时&#xff0c;是通过请求方法&#xff08;GET、Post、Put、Delete&#xff09;进行接口区分的&…...

探索与创作:2024年CSDN平台上的成长与突破

文章目录 我与CSDN的初次邂逅初学阶段的阅读CSDN&#xff1a;编程新手的避风港初学者的福音&#xff1a;细致入微的知识讲解考试复习神器&#xff1a;技术总结的“救命指南”曾经的自己&#xff1a;为何迟迟不迈出写博客的第一步兴趣萌芽&#xff1a;从“读”到“想写”的初体验…...

[Qualcomm]Qualcomm MDM9607 SDK代码下载操作说明

登录Qualcomm CreatePoing Qualcomm CreatePointhttps://createpoint.qti.qua...

【python_钉钉群发图片】

需求&#xff1a; **在钉钉群发图片&#xff0c;需要以图片的形式展示&#xff0c;如图所示&#xff1a;**但是目前影刀里面没有符合条件的指令 解决方法&#xff1a; 1、在钉钉开发者后台新建一个自建应用&#xff0c;发版&#xff0c;然后获取里面的appkey和appsecret&am…...

数据可视化:让数据讲故事的艺术

目录 1 前言2 数据可视化的基本概念2.1 可视化的核心目标2.2 传统可视化手段 3 数据可视化在知识图谱中的应用3.1 知识图谱的可视化需求3.2 知识图谱的可视化方法 4 数据可视化叙事&#xff1a;让数据讲故事4.1 叙事可视化的关键要素4.2 数据可视化叙事的实现方法 5 数据可视化…...

ElasticSearch下

DSL查询 叶子查询&#xff1a;在特定字段里查询特定值&#xff0c;属于简单查询&#xff0c;很少单独使用复合查询&#xff1a;以逻辑方式组合多个叶子查询或更改叶子查询的行为方式 在查询后还可以对查询结果做处理&#xff1a; 排序&#xff1a;按照1个或多个字段做排序分页…...

T-SQL语言的数据库交互

T-SQL语言的数据库交互 引言 随着信息技术的不断发展&#xff0c;数据库在各个行业中扮演着越来越重要的角色。数据库的有效管理和优化对于企业的数据安全、效率提升和决策支持至关重要。T-SQL&#xff08;Transact-SQL&#xff09;作为微软SQL Server的重要扩展语言&#xf…...

.Net 6.0 .Net7.0 .Net8.0 .Net9.0 使用 Serilog 按日志等级写入日志及 appsetting.json 配置方式实现

前言 最近使用最新版的Serilog记录日志时&#xff0c;发现以前有些关于Serilog的Nuget弃用了&#xff0c;最关键的是有些配置写法也改变&#xff0c;于是就整理了一下最新版的Serilog配置方式(appsetting.json)的使用 说明&#xff1a;我是用的.Net6&#xff0c;最新长期支持…...

[Qt]事件-鼠标事件、键盘事件、定时器事件、窗口改变事件、事件分发器与事件过滤器

目录 前言&#xff1a;Qt与操作系统的关系 一、Qt事件 1.事件介绍 2.事件的表现形式 常见的Qt事件&#xff1a; 常见的事件描述: 3.事件的处理方式 处理鼠标进入和离开事件案例 控件添加到对象树底层原理 二、鼠标事件 1.鼠标按下和释放事件&#xff08;单击&#x…...

从零开始:Gitee 仓库创建与 Git 配置指南

引言 Git 是一款广泛使用的版本控制工具&#xff0c;它能够帮助开发者在开发过程中高效地管理代码的版本。而 Gitee&#xff08;码云&#xff09;是国内知名的 Git 托管平台&#xff0c;它提供了强大的代码托管、团队协作和项目管理功能。如果你是 Git 和 Gitee 的新手&#x…...

大文件上传的解决办法~文件切片、秒传、限制文件并发请求。。。

1、项目背景&#xff1a;针对大文件上传&#xff0c;如果将文件作为一个请求去发送给后端&#xff0c;会有以下几种问题&#xff0c;首先是上传时间长&#xff0c;用户不能进行其他操作&#xff0c;包括页面刷新等操作&#xff0c;其次有的接口会设置响应时间限制&#xff0c;可…...

如何在日常工作中使用AI

### 如何在日常工作中使用AI&#xff1a;提高效率与创造力 随着人工智能&#xff08;AI&#xff09;技术的不断发展&#xff0c;它已经成为我们日常工作的重要助手。无论是在准备演示文稿、进行知识搜索还是寻求技术支持方面&#xff0c;AI都能够提供有力的支持。本文将探讨如何…...

计算机网络 (47)应用进程跨越网络的通信

前言 计算机网络应用进程跨越网络的通信是一个复杂而关键的过程&#xff0c;它涉及多个层面和组件的协同工作。 一、通信概述 计算机网络中的通信&#xff0c;本质上是不同主机中的应用进程之间的数据交换。为了实现这种通信&#xff0c;需要借助网络协议栈中的各层协议&#x…...

医疗集群系统中基于超融合数据库架构的应用与前景探析

一、引言 1.1 研究背景与意义 随着医疗信息化的飞速发展,医疗数据呈爆炸式增长。从日常诊疗记录、患者病历,到各类医疗影像、检查检验数据等,海量信息不断涌现。据统计,医疗数据的年增长率高达 30% 以上 ,2025 年,全球医疗数据量将达到 2314 艾字节(EB)。如此庞大的数…...

2024年度推进可解释人工智能迈向类人智能讨论总结分享

目录 一、探索“可解释人工智能”&#xff1a;AI如何从“黑箱”走向“透明大师” 二、走进可解释人工智能&#xff1a;让AI的决策变得透明 &#xff08;一&#xff09;几种常见的特征导向方法 &#xff08;二&#xff09;像素级方法 1. 层次相关传播&#xff08;LRP&#…...

【Unity】使用Canvas Group改变UI的透明度

目录 一、前言二、Canvas Group三、结合DOTween达到画面淡进的效果 一、前言 在平时开发中&#xff0c;可以通过控制材质、Color改变UI透明度&#xff0c;除此之外还可以CanvasGroup组件来控制透明度。 二、Canvas Group 官方文档链接&#x1f449;&#x1f449; 点击进入 …...

【北京迅为】iTOP-4412全能版使用手册-第八十七章 安装Android Studio

iTOP-4412全能版采用四核Cortex-A9&#xff0c;主频为1.4GHz-1.6GHz&#xff0c;配备S5M8767 电源管理&#xff0c;集成USB HUB,选用高品质板对板连接器稳定可靠&#xff0c;大厂生产&#xff0c;做工精良。接口一应俱全&#xff0c;开发更简单,搭载全网通4G、支持WIFI、蓝牙、…...

小例Java结合Spring框架和MyBatis ORM来实现 ERP项目中实现读写分离

前记&#xff1a;大家带着挑剔的眼光&#xff0c;多多批判和指正&#xff01;&#x1f64f; 在ERP项目中实现读写分离&#xff0c;我们可以使用Java结合Spring框架和MyBatis ORM来实现。以下是一个简化的例子&#xff0c;展示了如何在ERP项目中配置和使用读写分离。 一、项目…...

.gitignore配置忽略out目录

文章目录 说明操作 说明 可以结合IDEA可视化操作git&#xff0c;只要不删除远程仓库&#xff0c;如果本地操作项目出现错误&#xff0c;可以直接修改远程仓库的.gitignore文件&#xff0c;并重新拉取项目到本地。 操作 在项目根目录下找到 .gitignore 文件&#xff0c;打开并…...

mac 安装mongodb

本文分享2种mac本地安装mongodb的方法&#xff0c;一种是通过homebrew安装&#xff0c;一种是通过tar包安装 homebrew安装 brew tap mongodb/brew brew upate brew install mongodb-community8.0tar包安装 安装mongodb 1.下载mongodb社区版的tar包 mongdb tar包下载地址 2…...

向harbor中上传镜像(向harbor上传image)

向 Harbor 中上传镜像通常分为以下几个步骤&#xff1a; 1、登录 Harbor 2、构建镜像 3、标记镜像 4、推送镜像到 Harbor 仓库 1、登录 Harbor 首先&#xff0c;确保你已经能够访问 Harbor&#xff0c;并且已经注册了账户。如果还没有 Harbor 账户&#xff0c;你需要先注册一…...

项目太大导致 git clone 失败

git克隆也分深浅&#xff0c;大项目clone可以先用浅克隆&#xff0c;只克隆源代码和最新的提交记录。 具体分两步&#xff1a; 1. 浅克隆 git clone https://github.com/google/mydemo.git --depth 1 只会克隆最新的一次提交&#xff0c;没有历史记录&#xff0c; 2. 拉取剩…...