problem：把一个可重集分成两个互异的不为空集合，两个集合里面的数相乘的gcd为1（将集合中所有元素的质因数没有交集）
solution：显然本题并不是那么容易啊！考场上想了好久。。
其实转化为上面的题意就简单多了，对于每一个元素分解质因数，就是在筛质数的时候记下每一个合数的最小质因子low[x]，然后每一次不停的除low[x]
得到一个合数x'，然后继续除low[x']即可，然后我们统计出含有每一个质因子的数有哪些（用一个二维vector），然后具有同种质因子的数必须放在同一个集合里面，
也就是说他们可以合并在一起，考虑并查集处理，就把每一个质因子把对应的数全部合并在一起，然后最后统计剩下的没有交集的最终不能再合并的互异块的个数tot
考虑用tot分成两个不同的非空集合，显然是2 tot -2，快速幂处理即可。
复杂度O(n log n)
code:
# include <bits/stdc++.h>
# define int long long
# define pow Pow
using namespace std;
const int M=1e6+;
const int mo=1e9+;
bool prime[M];
int low[M],a[M],f[M],n;
vector<int>r[M];
inline int read()
{
int X=,w=; char c=;
while (!(c>=''&&c<='')) w|=c=='-',c=getchar();
while (c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
void getprime(int limit)
{
memset(low,,sizeof(low));
memset(prime,true,sizeof(prime));
for (int i=;i<=limit;i++) {
if (!prime[i]) continue;
for (int j=i+i;j<=limit;j+=i) {
if (low[j]==) low[j]=i;
prime[j]=false;
}
}
}
int father(int x)
{
if (f[x]==x) return x;
f[x]=father(f[x]);
return f[x];
}
int calc(int x,int y)
{
int fx=father(x),fy=father(y);
f[fx]=fy;
}
void solve(int id)
{
int num=a[id];
while (low[num]) {
r[low[num]].push_back(id);
int tmp=low[num];
while (num%tmp==) num/=tmp;
}
r[num].push_back(id);
}
int pow(int x,int n)
{
int ans=;
while (n) {
if (n&) ans=ans*x%mo;
x=x*x%mo;
n>>=;
}
return ans%mo;
}
signed main()
{
int T=read();
while (T--) {
n=read();
int MAX=;
for (int i=;i<=n;i++) {
a[i]=read(); f[i]=i;
MAX=max(MAX,a[i]);
}
getprime(MAX);
for (int i=;i<=M;i++) r[i].clear();
for (int i=;i<=n;i++) solve(i);
for (int i=;i<=M;i++) {
if (r[i].size()==) continue;
int k=r[i][];
for (int j=;j<r[i].size();j++) calc(k,r[i][j]);
}
int ret=;
for (int i=;i<=n;i++) if (f[i]==i) ret++;
printf("%lld\n",(pow(,ret)%mo-+mo)%mo);
}
return ;
}
sol:分成两组然后每一组的人都互相认识，显然想到对每一个联通块01染色分成不同的集合
对于每一个联通块统计出0的块的个数1的块的个数，显然0或者1的个数为n/2最好才会使 calc(i)+calc(n-i)最小
其中calc(x)=x(x-1)/2,
由于每一个块我们只能有1或者0，那么设f[i][j]表示前i个块，选择0或者1的块为j是否可能
转移的话就是
f[i][j]|=f[i-1][j-a[i].cnt0]|f[i-1][j-a[i].cnt1]
然后j从n/2向左枚举然后找到若f[n][j]合法
那么最小化 clac(j)+calc(n-j)即可
code：
# include <bits/stdc++.h>
# define int long long
using namespace std;
const int MAXN=;
int mp[MAXN][MAXN],n,m,col[MAXN];
bool f[MAXN][MAXN];
int cnt0,cnt1;
int o;
struct rec{ int cnt0,cnt1;}b[MAXN];
void dfs(int u,int fa,int c)
{
col[u]=c;
//printf("%d ; col=%d\n",u,col[u]);
if (c==) cnt0++; else cnt1++;
for (int v=;v<=n;v++) {
if (mp[u][v]==) continue;
if (col[v]!=-) {
if (col[v]!=c^) { puts("-1"); exit();}
else continue;
}
dfs(v,u,c^);
}
}
int calc(int x){ return x*(x-)/;}
signed main()
{
scanf("%lld%lld",&n,&m);
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
if (i==j) mp[i][j]=false;
else mp[i][j]=true;
while (m--) {
int u,v; scanf("%lld%lld",&u,&v);
mp[u][v]=mp[v][u]=false;
}
memset(col,-,sizeof(col));
for (int i=;i<=n;i++)
if (col[i]==-) {
cnt0=cnt1=;
dfs(i,-,);
b[++o].cnt1=cnt1;
b[++o].cnt0=cnt0;
}
//f[i][j]前i个集合，到达A中有j个是否成立
//f[i][j]|=f[i-1][j-b[i].cnt0]|f[i-1][j-b[i].cnt1]
memset(f,false,sizeof(f));
f[][b[].cnt1]=f[][b[].cnt0]=true;
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
f[i][j]=f[i][j]|f[i-][j-b[i].cnt0]|f[i-][j-b[i].cnt1];
int Ans=n*n*;
for (int i=;i<=n;i++)
if (f[n][i]) Ans=min(Ans,calc(i)+calc(n-i));
cout<<Ans<<endl;
return ;
}