题目 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.分布式处理:计算机网络的分布式处理是指将计算任务分散到网络中的多个节点(计算机或设备&…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
