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+10; const int mo=1e9+7; bool prime[M]; int low[M],a[M],f[M],n; vector<int>r[M]; inline int read() { int X=0,w=0; char c=0; while (!(c>='0'&&c<='9')) w|=c=='-',c=getchar(); while (c>='0'&&c<='9') X=(X<<1)+(X<<3)+(c^48),c=getchar(); return w?-X:X; } void getprime(int limit) { memset(low,0,sizeof(low)); memset(prime,true,sizeof(prime)); for (int i=2;i<=limit;i++) { if (!prime[i]) continue; for (int j=i+i;j<=limit;j+=i) { if (low[j]==0) 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==0) num/=tmp; } r[num].push_back(id); } int pow(int x,int n) { int ans=1; while (n) { if (n&1) ans=ans*x%mo; x=x*x%mo; n>>=1; } return ans%mo; } signed main() { int T=read(); while (T--) { n=read(); int MAX=0; for (int i=1;i<=n;i++) { a[i]=read(); f[i]=i; MAX=max(MAX,a[i]); } getprime(MAX); for (int i=1;i<=M;i++) r[i].clear(); for (int i=1;i<=n;i++) solve(i); for (int i=2;i<=M;i++) { if (r[i].size()==0) continue; int k=r[i][0]; for (int j=1;j<r[i].size();j++) calc(k,r[i][j]); } int ret=0; for (int i=1;i<=n;i++) if (f[i]==i) ret++; printf("%lld ",(pow(2,ret)%mo-2+mo)%mo); } return 0; }
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=1005; 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 ",u,col[u]); if (c==0) cnt0++; else cnt1++; for (int v=1;v<=n;v++) { if (mp[u][v]==0) continue; if (col[v]!=-1) { if (col[v]!=c^1) { puts("-1"); exit(0);} else continue; } dfs(v,u,c^1); } } int calc(int x){ return x*(x-1)/2;} signed main() { scanf("%lld%lld",&n,&m); for (int i=1;i<=n;i++) for (int j=1;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,-1,sizeof(col)); for (int i=1;i<=n;i++) if (col[i]==-1) { cnt0=cnt1=0; dfs(i,-1,1); 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[1][b[1].cnt1]=f[1][b[1].cnt0]=true; for (int i=2;i<=n;i++) for (int j=1;j<=n;j++) f[i][j]=f[i][j]|f[i-1][j-b[i].cnt0]|f[i-1][j-b[i].cnt1]; int Ans=n*n*2; for (int i=0;i<=n;i++) if (f[n][i]) Ans=min(Ans,calc(i)+calc(n-i)); cout<<Ans<<endl; return 0; }