A. X(质因数分解+并查集)
题意:给定一个序列,求的方案数,其中
,
,i和j属于两个不同集合内。
解法:考虑怎样必须将某几个数放进一个集合里。如果数列中全是1,那么每个数都是独立的,也就是可以随便拿出这之中的数字来组合集合,方案数,其中
,也就是
。
不难发现通性。如果两个数有质因子相同,那么它们一定不能在不一样的集合之中(要满足互质条件)。所以2,3,6;2,3,9;这一类数中有效的数只有两个点。也就是把所有有公共质因子的数放到一起。结合质因数分解,复杂度
错误点:
1.小范围数可以暴力筛出所有质数,记录每一个质数因子的对应质数,
,分解时直接分解
即可,可以做到
,比
的分解优秀许多
2.所有的1都要保留,其他根据公共质因子并查集合并
#include<bits/stdc++.h>
#pragma GCC optimze(3)
#define int long longusing namespace std;const int N = 1e6 + 10, mod = 1e9 + 7;int n,a[N],t[N],fa[N],minn[N];
vector<int> cnt[N];
map<int,int> mp;
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int _find(int x){if(fa[x]==x) return x;else return fa[x]=_find(fa[x]);
}
int poww(int a,int b){int res=1;while(b){if(b&1) res=(res*a)%mod; a=(a*a)%mod;b>>=1;}return res;
}
bool vis[N];
int pri[N],si;
void ai(){for(int i=2;i<=N;i++){if(!vis[i]){vis[i]=true;pri[++si]=i;mp[i]=si;for(int j=1;j<=N/i;j++){vis[i*j]=true;minn[i*j]=i;}}}
}void marge(int x,int y){int f1=_find(x),f2=_find(y);fa[_find(x)]=_find(y);
// cout<<x<<" "<<y<<" "<<f1<<" "<<f2<<endl;
}
void solve(){memset(fa,0,sizeof fa);n=read();for(int i=1;i<=si;i++) cnt[i].clear();memset(t,0,sizeof t);int mx=0;for(int i=1;i<=n;i++) a[i]=read(),mx=max(mx,a[i]);int ans=0,sum=0;for(int i=1;i<=n;i++){int x=a[i];while(x>1){int fac=minn[x];// cout<<fac<<' '<<x<<endl;while(x%fac==0){cnt[mp[fac]].push_back(a[i]);x/=fac;}}}
// cout<<_find(6)<<"CCf";for(int i=1;i<=n;i++) fa[a[i]]=a[i]; for(int i=1;i<=si;i++){for(int j=1;j<cnt[i].size();j++){int x=cnt[i][j-1],y=cnt[i][j];//cout<<x<<" "<<y<<endl;marge(x,y);}}for(int i=1;i<=n;i++){int x=_find(a[i]);//cout<<x<<" ";if(!t[x]||x==1){sum++;t[x]++;}}//cout<<sum<<endl;ans=(poww(2,sum)%mod-2+mod)%mod;cout<<ans<<endl;
}
signed main(){ai();int T;T=read();while(T--) solve(); return 0;
}
相关文章:
A. X(质因数分解+并查集)
题意:给定一个序列,求的方案数,其中,,i和j属于两个不同集合内。 解法:考虑怎样必须将某几个数放进一个集合里。如果数列中全是1,那么每个数都是独立的,也就是可以随便拿出这之中的数…...
自动化测试中如何应对网页弹窗的挑战!
在自动化测试中,网页弹窗的出现常常成为测试流程中的一个难点。无论是警告框、确认框、提示框,还是更复杂的模态对话框,都可能中断测试脚本的正常执行,导致测试结果的不确定性。本文将探讨几种有效的方法来应对网页弹窗的挑战&…...
Redission
一、Redis常见客户端 Jedis:简单,和命令最相似, API最丰富,多线程,不安全 SpringDataRedis: RedisTemplate,默认线程安全,底层基于Netty(异步支持),用于一…...
负载均衡详解
概述 负载均衡建立在现有的网络结构之上,提供了廉价、有效、透明的方式来扩展网络设备和服务器的带宽,增加了吞吐量,加强了网络数据的处理能力,提高了网络的灵活性和可用性。项目中常用的负载均衡有四层负载均衡和七层负载均衡。…...
Swift与UIKit:构建卓越用户界面的艺术
标题:Swift与UIKit:构建卓越用户界面的艺术 在iOS应用开发的世界中,UIKit是构建用户界面的基石。自从Swift语言问世以来,它与UIKit的结合就为开发者提供了一个强大而直观的工具集,用于创建直观、响应迅速的应用程序。…...
Spring 中ClassPathXmlApplicationContext
ClassPathXmlApplicationContext 是 Spring Framework 的一个重要类,位于 org.springframework.context.support 包中。它是 ApplicationContext 接口的实现,专门用于从类路径下加载 XML 配置文件。通过这个类,你可以在 Spring 应用程序中设置…...
Springboot邮件发送:如何配置SMTP服务器?
Springboot邮件发送集成方法?如何提升邮件发送性能? 对于使用Springboot的开发者来说,配置SMTP服务器来实现邮件发送并不是一件复杂的事情。AokSend将详细介绍如何通过配置SMTP服务器来实现Springboot邮件发送。 Springboot邮件发送&#x…...
二叉树--堆
二叉树-堆 一、堆的概念及结构1.1 堆的概念与结构1.2 堆的性质 二、堆的实现三、堆的应用1、堆排序 一、堆的概念及结构 1.1 堆的概念与结构 堆就是完全二叉树以顺序存储方式存储于一个数组中。 然后每一个根都大于它的左孩子和右孩子的堆,我们叫做大堆ÿ…...
【K8s】专题十二(2):Kubernetes 存储之 PersistentVolume
本文内容均来自个人笔记并重新梳理,如有错误欢迎指正! 如果对您有帮助,烦请点赞、关注、转发、订阅专栏! 专栏订阅入口 Linux 专栏 | Docker 专栏 | Kubernetes 专栏 往期精彩文章 【Docker】(全网首发)Kyl…...
python3多个图片合成一个pdf文件,生产使用验证过
简单的示例代码,展示如何将多个图片合成为一个 PDF 文件。 步骤 1: 安装依赖库 首先,确保你已经安装了 Pillow 和 reportlab 库: pip install Pillow reportlab步骤 2: 编写代码 下面是一个 Python 脚本,它将指定目录中的所有图片文件合成一个 PDF 文件: from PIL im…...
Stable Diffusion赋能“黑神话”——助力悟空走进AI奇幻世界
《黑神话:悟空》是由游戏科学公司制作的以中国神话为背景的动作角色扮演游戏,将于2024年8月20日发售。玩家将扮演一位“天命人”,为了探寻昔日传说的真相,踏上一条充满危险与惊奇的西游之路。 同时,我们还可以借助AI绘…...
微信小程序登陆
一 问题引入 我们之前的登陆都是:网页http传来请求,我们java来做这个请求的校验。 但是如果微信小程序登陆,就要用到相关的api来实现。 二 快速入门 1 引入依赖 官方依赖,在里面找合适的,去设置版本号。由于我这…...
SQL - 存储过程
假设你在开发一个应用,应用有一个数据库,你要在哪里写SQL语句?你不会在你的应用代码里写语句,它会让你的应用代码很混乱且难以维护。具体在哪里呢?在存储过程中或函数中。存储过程是一组为了完成特定功能的SQL语句集合…...
RabbitMQ环境搭建
2.5.RabbitMQ 安装 a.docker方式安装: 1.在我的docker学习笔记中具有详细的安装过程 b.rpm包方式安装: 1.MQ下载地址2.这里是提前下载好后上传安装包到服务器得opt目录下: 3.安装MQ需要先有Erlang语言环境,安装文件的Linux命令…...
多视点抓取(Multi-View Grasping)
目录 前言 一、在机器人抓取检测领域里,多视点抓取是什么意思 二、以GG-CNN为例,GG-CNN是怎么结合多个视点进行抓取预测的 前言 多视点抓取(Multi-View Grasping)是机器人抓取和检测领域的一个重要概念,它涉及到机器…...
【人工智能】对智元机器人发布的远征A1所应用的AI前沿技术进行详细分析,基于此整理一份学习教程。
智元机器人在其新品发布中应用了多项AI前沿技术。我们可以从以下几个方面来分析和整理这些技术,并基于此整理一份学习教程: 一、智元机器人应用的关键AI技术 自然语言处理 (NLP) 语音识别: 利用先进的语音识别技术,如OpenAI的Whisper&#x…...
影刀RPA--如何获取网页当页数据?
(1)点击数据抓取-选择需要获取数据的地方-会弹出是否是获取整个表格(当前页面) (2)点击“是”:则直接获取整个表格数据-点击完成即可 (3)点击“否”:如果你想…...
Bean对象生命周期流程图
Bean生命周期流程图:https://www.processon.com/view/link/5f8588c87d9c0806f27358c1 Spring扫描底层流程:https://www.processon.com/view/link/61370ee60e3e7412ecd95d43...
24/8/17算法笔记 策略梯度reinforce算法
import gym from matplotlib import pyplot as plt %matplotlib inline#创建环境 env gym.make(CartPole-v0) env.reset()#打印游戏 def show():plt.imshow(env.render(mode rgb_array))plt.show() show()定义网络模型 import torch #定义模型 model torch.nn.Sequential(t…...
【Linux学习】Linux开发工具——vim
🔥个人主页: Forcible Bug Maker 🔥专栏:Linux学习 目录 🌈前言🔥vim的基本概念🔥vim的基本操作🔥vim命令模式的命令集🔥简单vim配置⭐一键配置美观的vim安装方法卸载方…...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...
Python 高效图像帧提取与视频编码:实战指南
Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...
