手机网站建设的重点步骤,艺术字体在线生成器免费转换器,重庆地推团队外包,山东省建设工程网站题意#xff1a;给定一个序列#xff0c;求的方案数#xff0c;其中#xff0c;#xff0c;i和j属于两个不同集合内。
解法#xff1a;考虑怎样必须将某几个数放进一个集合里。如果数列中全是1#xff0c;那么每个数都是独立的#xff0c;也就是可以随便拿出这之中的数…题意给定一个序列求的方案数其中i和j属于两个不同集合内。
解法考虑怎样必须将某几个数放进一个集合里。如果数列中全是1那么每个数都是独立的也就是可以随便拿出这之中的数字来组合集合方案数其中也就是。
不难发现通性。如果两个数有质因子相同那么它们一定不能在不一样的集合之中要满足互质条件。所以236239这一类数中有效的数只有两个点。也就是把所有有公共质因子的数放到一起。结合质因数分解复杂度
错误点
1.小范围数可以暴力筛出所有质数记录每一个质数因子的对应质数分解时直接分解即可可以做到比的分解优秀许多
2.所有的1都要保留其他根据公共质因子并查集合并
#includebits/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];
vectorint cnt[N];
mapint,int mp;
int read(){int x0,f1;char chgetchar();while(ch0||ch9){if(ch-) f-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}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 res1;while(b){if(b1) res(res*a)%mod; a(a*a)%mod;b1;}return res;
}
bool vis[N];
int pri[N],si;
void ai(){for(int i2;iN;i){if(!vis[i]){vis[i]true;pri[si]i;mp[i]si;for(int j1;jN/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);
// coutx y f1 f2endl;
}
void solve(){memset(fa,0,sizeof fa);nread();for(int i1;isi;i) cnt[i].clear();memset(t,0,sizeof t);int mx0;for(int i1;in;i) a[i]read(),mxmax(mx,a[i]);int ans0,sum0;for(int i1;in;i){int xa[i];while(x1){int facminn[x];// coutfac xendl;while(x%fac0){cnt[mp[fac]].push_back(a[i]);x/fac;}}}
// cout_find(6)CCf;for(int i1;in;i) fa[a[i]]a[i]; for(int i1;isi;i){for(int j1;jcnt[i].size();j){int xcnt[i][j-1],ycnt[i][j];//coutx yendl;marge(x,y);}}for(int i1;in;i){int x_find(a[i]);//coutx ;if(!t[x]||x1){sum;t[x];}}//coutsumendl;ans(poww(2,sum)%mod-2mod)%mod;coutansendl;
}
signed main(){ai();int T;Tread();while(T--) solve(); return 0;
}
