F

题目链接:https://cn.vjudge.net/contest/275589#problem/F

题目大意:就是给你n个数,如果说两个数之间的gcd!=1,那么就将这两个点连起来,问你最终这些点能形成几块

具体思路:首先,我们可以讲所有数的倍数给标记出来,然后如果有一个数是 6,我们就把2 3 6 全部指向6,这样的话,每当我们找到一个数,我们就把这个数和他的素因子连起来(并查集),往小的地方连,然后最后看一下输入的n个数是不是标记的自己,如果是自己那么这肯定是一个块,如果不是标记的自己,就证明他所在的块已经被算过了(这也太暴力了...)

AC代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 # define inf 0x3f3f3f3f
 4 # define ll long long
 5 const int maxn = 1000000+100;
 6 int a[maxn],vis[maxn],father[maxn];
 7 vector<int>q[maxn];
 8 void init()
 9 {
10     for(int i=2; i<=maxn; i++)
11     {
12         for(int j=i*2; j<=maxn; j+=i)
13         {
14             q[j].push_back(i);
15         }
16     }
17 }
18 int Find(int t)
19 {
20     return t==father[t]?t:father[t]=Find(father[t]);
21 }
22 void cal(int t1,int t2)
23 {
24     int x1=Find(t1);
25     int y1=Find(t2);
26     if(x1!=y1)
27     {
28         if(x1>y1)father[x1]=y1;
29         else father[y1]=x1;
30     }
31 }
32 int main()
33 {
34     init();
35     int T;
36     scanf("%d",&T);
37     int Case=0;
38     while(T--)
39     {
40         int n;
41         scanf("%d",&n);
42         for(int i=1; i<=maxn; i++)
43         {
44             father[i]=i;
45         }
46         memset(vis,0,sizeof(vis));
47         for(int i=1; i<=n; i++)
48         {
49             scanf("%d",&a[i]);
50             int len=q[a[i]].size();
51             for(int j=0; j<len; j++)
52             {
53                 cal(a[i],q[a[i]][j]);
54             }
55         }
56         ll ans=0;
57         for(int i=1; i<=n; i++)
58         {
59             if(a[i]==1)
60             {
61                 ans++;
62                 continue;
63             }
64             int t=Find(a[i]);
65             if(vis[t])continue;
66             vis[t]=1;
67             ans++;
68         }
69         printf("Case %d: %lld
",++Case,ans);
70     }
71     return 0;
72 }
73