题意：

　　每两个点如果他们的gcd大于1的话就可以连一条边，问在这些数里面有多少个联通块。

题解：

　　我们可以用筛法倍数。然后用并查集将他们连通起来，2 3 6 本来2 和3的gcd 为1，但是他们可以通过6使得连通。

　　还有就是要注意 15 25 35 这个数据。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 12 using namespace std;13 typedef long long LL;14 typedef unsigned long long uLL;15 #define ms(a, b) memset(a, b, sizeof(a))16 #define pb push_back17 #define mp make_pair18 #define eps 0.000000000119 #define IOS ios::sync_with_stdio(0);cin.tie(0);20 const LL INF = 0x3f3f3f3f3f3f3f3f;21 const int inf = 0x3f3f3f3f;22 const int mod = 1e9+7;23 const int maxn = 1000000+10;24 int num[maxn];25 int F[maxn];26 vector 
                 
                   now;27 int findfa(int x)28 {29 if(F[x]==x){30 return x;31 }32 else return F[x] = findfa(F[x]);33 }34 int join(int x, int y)35 {36 int f1 = findfa(x);37 int f2 = findfa(y);38 if(f1!=f2){39 if(f1>f2) swap(f1, f2);40 F[f2] = f1;41 }42 }43 void solve()44 {45 ms(num, 0);46 for(int i = 2;i
                  
                   =2){61 for(int k = 1;k

View Code

转载于:https://www.cnblogs.com/denghaiquan/p/7287020.html

你可能感兴趣的文章