当前位置：首页 > news >正文

A. X（质因数分解+并查集）

news 2025/7/24 4:58:52

题意：给定一个序列，求 $gcd(x,y)=1$ 的方案数，其中 $x=\prod ai$ ， $y=\prod aj$ ，i和j属于两个不同集合内。

解法：考虑怎样必须将某几个数放进一个集合里。如果数列中全是1，那么每个数都是独立的，也就是可以随便拿出这之中的数字来组合集合，方案数 $\sum_{i=1}^{sum-1}C(sum,i)$ ，其中 $C(x,y)=fac[x]*inv[y]*inv[x-y]$ ，也就是 $2^{sum}-2$ 。

不难发现通性。如果两个数有质因子相同，那么它们一定不能在不一样的集合之中（要满足互质条件）。所以2，3，6；2，3，9；这一类数中有效的数只有两个点。也就是把所有有公共质因子的数放到一起。结合质因数分解，复杂度 $O(nlogn)$

错误点：

1.小范围数 $ai<=1e6$ 可以暴力筛出所有质数，记录每一个质数因子的对应质数， $pri[i*j]=i$ ，分解时直接分解 $pri[x]$ 即可，可以做到 $O(logn)$ ，比 $O({n_{}}^{1/2}{})O(n)$ 的分解优秀许多

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;
}

查看全文

http://www.lryc.cn/news/428674.html