题目 3220 ⭐因数计数⭐【数理基础】蓝桥杯2024年第十五届省赛
小蓝随手写出了含有 n n n 个正整数的数组 a 1 , a 2 , ⋅ ⋅ ⋅ , a n {a_1, a_2, · · · , a_n} a1,a2,⋅⋅⋅,an ,他发现可以轻松地算出有多少个有序二元组 ( i , j ) (i, j) (i,j) 满足 a j a_j aj 是 a i a_i ai 的一个因数。因此他定义一个整数对 ( x 1 , y 1 ) (x_1, y_1) (x1,y1) 是一个整数对 ( x 2 , y 2 ) (x_2, y_2) (x2,y2) 的“因数”当且仅当 x 1 x_1 x1 和 y 1 y_1 y1 分别是 x 2 x_2 x2 和 y 2 y_2 y2的因数。他想知道有多少个有序四元组 ( i , j , k , l ) (i, j, k, l) (i,j,k,l) 满足 ( a i , a j ) (a_i, a_j) (ai,aj) 是 ( a k , a l (a_k, a_l (ak,al) 的因数,其中 i , j , k , l i, j, k, l i,j,k,l 互不相等。
问题分析:
我们需要找到所有满足以下条件的有序四元组 ( i , j , k , l ) (i, j, k, l) (i,j,k,l):
- ( a i , a j ) (a_i, a_j) (ai,aj) 是 ( a k , a l ) (a_k, a_l) (ak,al) 的因数,即:
- a i a_i ai 是 a k a_k ak 的因数。
- a j a_j aj 是 a l a_l al 的因数。
- i , j , k , l i, j, k, l i,j,k,l 互不相等。
解决思路:
- 统计每个数的因数关系:
- 对于数组中的每个数 x x x,统计有多少个数是 x x x 的因数。遍历数组,对于每个数 x x x,遍历所有可能的因数 d d d( d d d 从 1 到 s q r t ( x ) sqrt(x) sqrt(x)),如果 d d d 是 x x x 的因数,则记录 d d d 和 x / d x/d x/d。
- 使用一个哈希表或数组
factor_count来记录每个数的因数个数。
- 枚举四元组:
- 对于每一对 ( a k , a l ) (a_k, a_l) (ak,al),找到所有满足 a i a_i ai 是 a k a_k ak 的因数且 a j a_j aj 是 a l a_l al 的因数的 ( a i , a j ) (a_i, a_j) (ai,aj)。
- 由于 i , j , k , l i, j, k, l i,j,k,l 必须互不相等,需要排除重复的情况。
- 计算结果:
- 对于每一对 ( a k , a l ) (a_k, a_l) (ak,al),计算满足条件的 ( a i , a j ) (a_i, a_j) (ai,aj) 的数量,并累加到结果中。
- 如果 a k a_k ak 和 a l a_l al 的因数中包含本身,需要减去重复的情况。
#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;// 统计每个数的因数个数
unordered_map<int, int> countFactors(const vector<int>& nums) {unordered_map<int, int> factor_count;for (int x : nums) {int count = 0;for (int d = 1; d <= sqrt(x); d++) {if (x % d == 0) {count++;if (d != x / d) {count++;}}}factor_count[x] = count;}return factor_count;
}// 计算满足条件的四元组数量
int countValidQuadruples(const vector<int>& nums) {int n = nums.size();if (n < 4) return 0;// 统计每个数的因数个数unordered_map<int, int> factor_count = countFactors(nums);int result = 0;for (int k = 0; k < n; k++) {for (int l = 0; l < n; l++) {if (k == l) continue; // 确保 k 和 l 不相等int ak = nums[k];int al = nums[l];// 计算满足 ai 是 ak 的因数且 aj 是 al 的因数的 (ai, aj) 的数量int count_ai = factor_count[ak];int count_aj = factor_count[al];// 排除 ai 或 aj 等于 ak 或 al 的情况if (ak % ak == 0 && al % al == 0) {count_ai--;count_aj--;}result += count_ai * count_aj;}}return result;
}
复杂度分析:
- 时间复杂度:
- 预处理因数关系: O ( n ∗ m a x _ n u m ) O(n * \sqrt{max\_num}) O(n∗max_num),其中 n n n 是数组长度, m a x _ n u m max\_num max_num 是数组中的最大值。
- 枚举四元组: O ( n 2 ) O(n^2) O(n2)。
- 总时间复杂度: O ( n 2 + n ∗ m a x _ n u m ) O(n^2 + n * \sqrt{max\_num}) O(n2+n∗max_num)。
- 空间复杂度:
- 哈希表
factor_count的空间复杂度为 O ( n ) O(n) O(n)。
- 哈希表
相关文章:
题目 3220 ⭐因数计数⭐【数理基础】蓝桥杯2024年第十五届省赛
小蓝随手写出了含有 n n n 个正整数的数组 a 1 , a 2 , ⋅ ⋅ ⋅ , a n {a_1, a_2, , a_n} a1,a2,⋅⋅⋅,an ,他发现可以轻松地算出有多少个有序二元组 ( i , j ) (i, j) (i,j) 满足 a j a_j aj 是 a i a_i ai 的一个因数。因此他定义一个整数对 …...
【Java代码审计 | 第十一篇】SSRF漏洞成因及防范
未经许可,不得转载。 文章目录 SSRF漏洞成因Java中发送HTTP请求的函数1、HttpURLConnection2、HttpClient(Java 11)3、第三方库Request库漏洞示例OkHttpClient漏洞示例HttpClients漏洞示例 漏洞代码示例防范标准代码 SSRF SSRF(S…...
RabbitMQ高级特性--消息确认机制
目录 一、消息确认 1.消息确认机制 2.手动确认方法 二、代码示例 1. AcknowledgeMode.NONE 1.1 配置文件 1.2 生产者 1.3 消费者 1.4 运行程序 2.AcknowledgeMode.AUTO 3.AcknowledgeMode.MANUAL 一、消息确认 1.消息确认机制 生产者发送消息之后,到达消…...
C++复试笔记(一)
Setw 是C中用于设置输出字段宽度的函数。当使用 setw(3) 时,它会设置紧接着的输出字段的最小宽度为3个字符。如果字段内容长度小于3,则会在左侧填充空格以达到指定宽度;如果内容长度大于或等于3,则全部内容将被输出,…...
K8s 1.27.1 实战系列(四)验证集群及应用部署测试
一、验证集群可用性 1、检查节点 kubectl get nodes ------------------------------------------------------ NAME STATUS ROLES AGE VERSION k8s-master Ready control-plane 3h48m v1.27.1 k8s-node1 Ready <none> …...
基于Spring Boot的健美操评分管理系统设计与实现(LW+源码+讲解)
专注于大学生项目实战开发,讲解,毕业答疑辅导,欢迎高校老师/同行前辈交流合作✌。 技术范围:SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容:…...
H5页面在移动端自动横屏
首先需要再head标签添加这样一段代码 <meta name="viewport" content="width=device-width,height=device-width,initial-scale=1.0,user-scalable=no">因为需求是为了满足WEB端和手机端都可以查看整体效果 但由于UI没有设计移动端的样式 所以我想说…...
【从0到1搞懂大模型】神经网络的实现:数据策略、模型调优与评估体系(3)
一、数据集的划分 (1)按一定比例划分为训练集和测试集 我们通常取8-2、7-3、6-4、5-5比例切分,直接将数据随机划分为训练集和测试集,然后使用训练集来生成模型,再用测试集来测试模型的正确率和误差,以验证…...
从0到1入门RabbitMQ
一、同步调用 优势:时效性强,等待到结果后才返回 缺点: 拓展性差性能下降级联失败问题 二、异步调用 优势: 耦合度低,拓展性强异步调用,无需等待,性能好故障隔离,下游服务故障不影响…...
MySQL数据库复杂的增删改查操作
在前面的文章中,我们主要学习了数据库的基础知识以及基本的增删改查的操作。接下去将以一个比较实际的公司数据库为例子,进行讲解一些较为复杂且现时需求的例子。 基础知识: 一文清晰梳理Mysql 数据库基础知识_字段变动如何梳理清楚-CSDN博…...
点云软件VeloView开发环境搭建与编译
官方编译说明 LidarView / LidarView-Superbuild GitLab 我的编译过程: 安装vs2019,windows sdk,qt5.14.2(没安装到5.15.7),git,cmake3.31,python3.7.9,ninja下载放到…...
本地YARN集群部署
请先完成HDFS的前置部署,部署方式可查看:本地部署HDFS集群https://blog.csdn.net/m0_73641796/article/details/145998092?spm1001.2014.3001.5502 部署说明 组件配置文件启动进程备注Hadoop HDFS需修改 需启动: NameNode作为主节点 DataNode作为从节点 Secondary…...
STM32常见外设的驱动示例和代码解析
以下是针对STM32常见外设的驱动示例和代码解析,基于HAL库实现,适用于大多数STM32系列(如F1/F4/H7等),可根据具体型号调整引脚和时钟配置。 1. GPIO驱动 应用场景:控制LED、按键检测、继电器开关等。 示例代码: // 初始化LED(推挽输出) void LED_Init(void) {GPIO_In…...
使用数据库和缓存的时候,是如何解决数据不一致的问题的?
1.缓存更新策略 1.1. 缓存旁路模式(Cache Aside) 在应用里负责管理缓存,读取时先查缓存,如果命中了则返回缓存,如果未命中就查询数据库,然后返回缓存,返回缓存的同时把数据给写入缓存中。更新…...
VS Code C++ 开发环境配置
VS Code 是当前非常流行的开发工具. 本文讲述如何配置 VS Code 作为 C开发环境. 本文将按照如下步骤来介绍如何配置 VS Code 作为 C开发环境. 安装编译器安装插件配置工作区 第一个步骤的具体操作会因为系统不同或者方案不同而有不同的选择. 环境要求 首先需要立即 VS Code…...
使用OpenCV和MediaPipe库——实现人体姿态检测
目录 准备工作如何在Windows系统中安装OpenCV和MediaPipe库? 安装Python 安装OpenCV 安装MediaPipe 验证安装 代码逻辑 整体代码 效果展示 准备工作如何在Windows系统中安装OpenCV和MediaPipe库? 安装Python 可以通过命令行运行python --versio…...
JWT的学习
1、HTTP无状态及解决方案 HTTP一种是无状态的协议,每次请求都是一次独立的请求,一次交互之后就是陌生人。 以CSDN为例,先登录一次,然后浏览器退出,这个时候在进入CSDN,按理说服务器是不知道你已经登陆了&…...
elasticsearch是哪家的
Elasticsearch:数据搜索与分析的领航者 在当今这个信息爆炸的时代,快速且准确地处理海量数据成为了众多企业和组织追求的目标。而Elasticsearch正是在这个背景下脱颖而出的一款强大的开源搜索引擎。它是由位于美国加利福尼亚州的Elastic公司所开发和维护…...
《A++ 敏捷开发》- 18 软件需求
需求并不是关于需求 (Requirements are not really about requirements) 大家去公共图书馆寄存物品,以前都是扫二维码开箱,有些图书馆升级了使用指纹识别。 “是否新方法比以前好?”我问年轻的开发人员。 “当然用指纹识别好。新技术&#x…...
计算机网络:计算机网络的组成和功能
计算机网络的组成: 计算机网络的工作方式: 计算机网络的逻辑功能; 总结: 计算机网络的功能: 1.数据通信 2.资源共享 3.分布式处理:计算机网络的分布式处理是指将计算任务分散到网络中的多个节点(计算机或设备&…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
