题目 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.分布式处理:计算机网络的分布式处理是指将计算任务分散到网络中的多个节点(计算机或设备&…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
Windows安装Miniconda
一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...
