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

题目 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(nmax_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+nmax_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​ &#xff0c;他发现可以轻松地算出有多少个有序二元组 ( i , j ) (i, j) (i,j) 满足 a j a_j aj​ 是 a i a_i ai​ 的一个因数。因此他定义一个整数对 …...

【Java代码审计 | 第十一篇】SSRF漏洞成因及防范

未经许可&#xff0c;不得转载。 文章目录 SSRF漏洞成因Java中发送HTTP请求的函数1、HttpURLConnection2、HttpClient&#xff08;Java 11&#xff09;3、第三方库Request库漏洞示例OkHttpClient漏洞示例HttpClients漏洞示例 漏洞代码示例防范标准代码 SSRF SSRF&#xff08;S…...

RabbitMQ高级特性--消息确认机制

目录 一、消息确认 1.消息确认机制 2.手动确认方法 二、代码示例 1. AcknowledgeMode.NONE 1.1 配置文件 1.2 生产者 1.3 消费者 1.4 运行程序 2.AcknowledgeMode.AUTO 3.AcknowledgeMode.MANUAL 一、消息确认 1.消息确认机制 生产者发送消息之后&#xff0c;到达消…...

C++复试笔记(一)

Setw 是C中用于设置输出字段宽度的函数。当使用 setw(3) 时&#xff0c;它会设置紧接着的输出字段的最小宽度为3个字符。如果字段内容长度小于3&#xff0c;则会在左侧填充空格以达到指定宽度&#xff1b;如果内容长度大于或等于3&#xff0c;则全部内容将被输出&#xff0c;…...

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+源码+讲解)

专注于大学生项目实战开发,讲解,毕业答疑辅导&#xff0c;欢迎高校老师/同行前辈交流合作✌。 技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;…...

H5页面在移动端自动横屏

首先需要再head标签添加这样一段代码 <meta name="viewport" content="width=device-width,height=device-width,initial-scale=1.0,user-scalable=no">因为需求是为了满足WEB端和手机端都可以查看整体效果 但由于UI没有设计移动端的样式 所以我想说…...

【从0到1搞懂大模型】神经网络的实现:数据策略、模型调优与评估体系(3)

一、数据集的划分 &#xff08;1&#xff09;按一定比例划分为训练集和测试集 我们通常取8-2、7-3、6-4、5-5比例切分&#xff0c;直接将数据随机划分为训练集和测试集&#xff0c;然后使用训练集来生成模型&#xff0c;再用测试集来测试模型的正确率和误差&#xff0c;以验证…...

从0到1入门RabbitMQ

一、同步调用 优势&#xff1a;时效性强&#xff0c;等待到结果后才返回 缺点&#xff1a; 拓展性差性能下降级联失败问题 二、异步调用 优势&#xff1a; 耦合度低&#xff0c;拓展性强异步调用&#xff0c;无需等待&#xff0c;性能好故障隔离&#xff0c;下游服务故障不影响…...

MySQL数据库复杂的增删改查操作

在前面的文章中&#xff0c;我们主要学习了数据库的基础知识以及基本的增删改查的操作。接下去将以一个比较实际的公司数据库为例子&#xff0c;进行讲解一些较为复杂且现时需求的例子。 基础知识&#xff1a; 一文清晰梳理Mysql 数据库基础知识_字段变动如何梳理清楚-CSDN博…...

点云软件VeloView开发环境搭建与编译

官方编译说明 LidarView / LidarView-Superbuild GitLab 我的编译过程&#xff1a; 安装vs2019&#xff0c;windows sdk&#xff0c;qt5.14.2&#xff08;没安装到5.15.7&#xff09;&#xff0c;git&#xff0c;cmake3.31&#xff0c;python3.7.9&#xff0c;ninja下载放到…...

本地YARN集群部署

请先完成HDFS的前置部署&#xff0c;部署方式可查看:本地部署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. 缓存旁路模式&#xff08;Cache Aside&#xff09; 在应用里负责管理缓存&#xff0c;读取时先查缓存&#xff0c;如果命中了则返回缓存&#xff0c;如果未命中就查询数据库&#xff0c;然后返回缓存&#xff0c;返回缓存的同时把数据给写入缓存中。更新…...

VS Code C++ 开发环境配置

VS Code 是当前非常流行的开发工具. 本文讲述如何配置 VS Code 作为 C开发环境. 本文将按照如下步骤来介绍如何配置 VS Code 作为 C开发环境. 安装编译器安装插件配置工作区 第一个步骤的具体操作会因为系统不同或者方案不同而有不同的选择. 环境要求 首先需要立即 VS Code…...

使用OpenCV和MediaPipe库——实现人体姿态检测

目录 准备工作如何在Windows系统中安装OpenCV和MediaPipe库&#xff1f; 安装Python 安装OpenCV 安装MediaPipe 验证安装 代码逻辑 整体代码 效果展示 准备工作如何在Windows系统中安装OpenCV和MediaPipe库&#xff1f; 安装Python 可以通过命令行运行python --versio…...

JWT的学习

1、HTTP无状态及解决方案 HTTP一种是无状态的协议&#xff0c;每次请求都是一次独立的请求&#xff0c;一次交互之后就是陌生人。 以CSDN为例&#xff0c;先登录一次&#xff0c;然后浏览器退出&#xff0c;这个时候在进入CSDN&#xff0c;按理说服务器是不知道你已经登陆了&…...

elasticsearch是哪家的

Elasticsearch&#xff1a;数据搜索与分析的领航者 在当今这个信息爆炸的时代&#xff0c;快速且准确地处理海量数据成为了众多企业和组织追求的目标。而Elasticsearch正是在这个背景下脱颖而出的一款强大的开源搜索引擎。它是由位于美国加利福尼亚州的Elastic公司所开发和维护…...

《A++ 敏捷开发》- 18 软件需求

需求并不是关于需求 (Requirements are not really about requirements) 大家去公共图书馆寄存物品&#xff0c;以前都是扫二维码开箱&#xff0c;有些图书馆升级了使用指纹识别。 “是否新方法比以前好&#xff1f;”我问年轻的开发人员。 “当然用指纹识别好。新技术&#x…...

计算机网络:计算机网络的组成和功能

计算机网络的组成&#xff1a; 计算机网络的工作方式&#xff1a; 计算机网络的逻辑功能; 总结&#xff1a; 计算机网络的功能&#xff1a; 1.数据通信 2.资源共享 3.分布式处理:计算机网络的分布式处理是指将计算任务分散到网络中的多个节点&#xff08;计算机或设备&…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...