题意：给定一个序列，求的方案数，其中
，
，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;
}
)
