Prime Independence
2024-09-08 15:36:53
题意:
对于给定集合,求解最大的子集合,使得集合内两两之商不为质数。
解法:
考虑对于每一个数字分解质因数可以得到 $O(nloglogNUM)$ 条两个数字不可以出现在同一集合的信息。
同时发现一条代表冲突的边必然是联结一个由奇数个质数连乘构成的数字和一个由偶数个质数连乘构成的数字。
是一个二分图,考虑最大独立集即可。
#include <bits/stdc++.h> const int N = ; using namespace std; int n,timnow;
int pre[N],a[N],v[N],cnt[N],Id[];
vector<int> g[N],fac[N]; bool find(int x)
{
for(int i=;i<(int)g[x].size();i++)
{
int p = g[x][i];
if(v[p] == timnow) continue;
v[p] = timnow;
if(!pre[p] || find(pre[p]))
{
pre[p] = x;
return ;
}
}
return ;
} int main()
{
int T,Te = ;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<=n;i++) g[i].clear(),pre[i] = ,fac[i].clear(),cnt[i]=;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
Id[a[i]] = i;
int tmp = a[i];
for(int j=;j*j<=a[i];j++)
if(tmp%j==)
{
fac[i].push_back(j);
while(tmp%j==) tmp/=j, cnt[i]++;
}
if(tmp>) fac[i].push_back(tmp), cnt[i]++;
}
for(int i=;i<=n;i++)
{
for(int j=;j<(int)fac[i].size();j++)
{
int tmp = a[i]/fac[i][j];
if(Id[tmp])
{
int k = Id[tmp];
if(cnt[i]&) g[i].push_back(k);
else g[k].push_back(i);
}
}
}
int ans = ;
for(int i=;i<=n;i++)
{
timnow ++;
if(find(i)) ans++;
Id[a[i]] = ;
}
printf("Case %d: %d\n", ++Te, n-ans);
}
return ;
}
最新文章
- Oracle学习笔记二 初识Oracle(二)
- Easy UI 面板
- Android APK 文件自动安装
- 手动删除webapps下项目,导致Document base %TOMCAT_HOME%\webapps\XXX does not exist or is not a readable directory
- HTML5自学笔记[ 7 ]defer和async
- JS正则表达式基础
- Javascript模块化编程系列三: CommonJS &; AMD 模块化规范描述
- ASIFormDataRequest实现post的代码示例
- HDU3466-Proud Merchants(01背包变形)
- C#学习笔记(4)
- OSS研究
- 深入理解maven与应用(二):灵活的构建
- uploadify在IE6下的问题
- linux下ssh端口的修改和登录
- 跨域,json与jsonp格式
- Linux上网问题
- 金蝶K/3 固定置产相关SQL语句
- python画高斯分布图形
- 【OpenCV】SIFT原理与源码分析:DoG尺度空间构造
- c++11并行、并发与多线程编程