fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define INF 1000000000
  3. #define M 1000000007
  4. #define ll long long
  5. #define MAX 10000001
  6. using namespace std;
  7.  
  8. int a[MAX],m[MAX];
  9. int par[MAX],rank[MAX];
  10.  
  11. int getroot(int x){
  12.     if (par[x]==x) return x;
  13.     else return getroot(par[x]);
  14. }
  15.  
  16. int union_(int x,int y){
  17.     int rx = getroot(x);
  18.     int ry = getroot(y);
  19.     if (rx==ry) return 0;
  20.     if (rank[rx]>rank[ry]){
  21.         par[ry] = rx;
  22.         rank[rx]++;
  23.     }
  24.     else{
  25.         par[rx] = ry;
  26.         rank[ry]++;
  27.     }
  28.     return 0;
  29. }
  30.  
  31. int main(){
  32.     int n;
  33.     cin >> n;
  34.     for (int i=0;i<n;i++){
  35.         int x;scanf("%d",&x);
  36.         m[x] = 1;
  37.     }
  38.     n = 0;
  39.     for (int i=1;i<MAX;i++){
  40.         if (m[i]){
  41.             a[n++] = i;
  42.             par[i] = i;
  43.         }
  44.     }
  45.     int groups = n;
  46.     int md = 0;
  47.     ll sum = 0;
  48.     while(groups!=1){
  49.         for (int i=0;i<n;i++){
  50.             for (int j=a[i]+md;j<MAX;j+=a[i]){
  51.                 if (m[j] && getroot(a[i])!=getroot(j)){
  52.                     union_(j,a[i]);
  53.                     sum+=md;
  54.                     groups--;
  55.                 }
  56.             }
  57.         }
  58.         md++;
  59.     }
  60.     cout << sum << endl;
  61.     return 0;
  62. }
Runtime error #stdin #stdout 0s 159744KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KZgFl4
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!