Problem Description

給你n個整數(shù)，a1,a2,a3,......,an。每個整數(shù)范圍1到1e6。選取任意的i（1<=i<=n）和j（1<=j<=n）如果gcd（ai,aj）>1，ai和aj為一組，如果ai和aj為一組，ai和ak為一組，那么ai,aj,ak為一組，求這n個整數(shù)中，最后有多少個組。

Input

輸入一個T表示組數(shù)（T<=100）。然后輸入一個整數(shù)n（1<=n<=1e5）,最后輸入n個整數(shù)ai（1<=ai<=1e6）。

Output

每一組測試樣例輸出一個整數(shù)，表示一共有多少組。

Sample Input

2 3 2 3 4 6 2 3 4 5 6 6

Sample Output

2 2

題解思路：

唯一分解定理+并查集

唯一分解定理：每一個數(shù)都可以分解為素數(shù)的乘積;

篩一下1e6范圍內(nèi)的素數(shù)，將數(shù)字拆分為素數(shù)(要用sqrt()的時間);

并查集維護(hù)關(guān)系;

選拔賽的題目? 還是好菜 自己

#include<bits/stdc++.h>#define mem(a,b) memset(a,b,sizeof(a))using namespace std;const int maxn=1e6+80000;int prime[maxn],tot=0;bool is_prime[maxn],vis[maxn];//數(shù)字?jǐn)?shù)否出現(xiàn)int f[maxn];int root(int x) {if(x==f[x]) return f[x];else return f[x]=root(f[x]); }void make_prime()//歐拉篩 {is_prime[1]=is_prime[0]=true;for(int i=2;i<=1e6;i++){if(!is_prime[i]){prime[++tot]=i;}for(int j=1;j<=tot&&i*prime[j]<=1e6;j++){is_prime[i*prime[j]]=true;if(i%prime[j]==0){break;}}} }int main(){make_prime(); // for(int i=1;i<=30;i++) // { // cout<<prime[i]<<endl; // }int t;scanf("%d",&t);while(t--){int n,now;mem(vis,false);scanf("%d",&n);for(int i=1;i<=n+tot;i++){f[i]=i;}for(int i=1;i<=n;i++){scanf("%d",&now);vis[i]=true;for(int j=1;j<=tot&&(prime[j]*prime[j]<=now);j++)//根下拆分{if(!(now%prime[j])){vis[n+j]=true;int x=root(i),y=root(n+j);f[x]=y;while(!(now%prime[j]))now/=prime[j];}}if(now!=1)//如果拆到最后不是1 說明now為一個比根下now大的素數(shù){int x=root(i);int y=n+lower_bound(prime+1,prime+1+tot,now)-prime;vis[y]=true;y=root(y);f[x]=y;}}int ans=0; // for(int i=1;i<=6;i++) // { // cout<<f[i]<<" "<<vis[i]<<endl; // }for(int i=1;i<=n+tot;i++){if(f[i]==i&&vis[i]){ans++;}}printf("%d\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的sdut 4408 这真的是签到题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。