fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(ac) ac.begin(), ac.end()
  4. #define fi first
  5. #define se second
  6. #define pii pair <int, int>
  7. #define task "tet"
  8. #define db double
  9. #define pb push_back
  10. #define eb emplace_back
  11. #define MASK(x) (1 << x)
  12. #define ll long long
  13. #define pll pair <ll, ll>
  14. #define bit(i, j) ((i >> j) & 1)
  15.  
  16. const int N = 1e6;
  17. vector <int> d[N + 1], g[N + 1];
  18. int vis[N + 1];
  19.  
  20. void sang() {
  21.     for(int i=2;i<=500000;i++) {
  22.         for(int j=(i << 1);j<=N;j+=i) d[j].eb(i);
  23.     }
  24.     return;
  25. }
  26.  
  27. struct DSU {
  28.     int n;
  29.     vector <int> lab;
  30.  
  31.     DSU(int n): n(n), lab(n + 1, -1) {}
  32.  
  33.     int find(int u) {return lab[u] < 0 ? u : lab[u] = find(lab[u]);}
  34.  
  35.     bool join(int a, int b) {
  36.         a = find(a);
  37.         b = find(b);
  38.         if(a != b) {
  39.             if(lab[a] > lab[b]) swap(a, b);
  40.             lab[a] += lab[b];
  41.             lab[b] = a;
  42.             return true;
  43.         }
  44.         return false;
  45.     }
  46. };
  47.  
  48. int32_t main() {
  49. 	ios::sync_with_stdio(false);
  50. 	cin.tie(0), cout.tie(0);
  51. 	if(fopen(task".inp", "r")) {
  52. 		freopen(task".inp", "r", stdin);
  53. 		freopen(task".out", "w", stdout);
  54. 	}
  55.  
  56.     int n; cin >> n;
  57.     ll res = 0;
  58.     int mst = 1;
  59.     int lim = 0;
  60.     DSU dsu(n);
  61.     sang();
  62.     for(int i=1;i<=n;i++) {
  63.         int x; cin >> x;
  64.         if(vis[x] > 0) {
  65.             res += x;
  66.             mst++;
  67.             dsu.join(i, vis[x]);
  68.             continue;
  69.         }
  70.         vis[x] = i;
  71.         for(int &v : d[x]) g[v].eb(i);
  72.         if(x > 1) g[x].eb(i);
  73.         lim = max(lim, x);
  74.     }
  75.  
  76.     for(int i=lim;i>=2;i--) if(g[i].size() > 1) {
  77.         int last = g[i].back();
  78.         g[i].pop_back();
  79.         for(int &v : g[i]) if(dsu.join(last, v) == true) {
  80.             res += i;
  81.             mst++;
  82.             if(mst == n) break;
  83.         }
  84.         if(mst == n) break;
  85.     }
  86.  
  87.     cout << res + n - mst;
  88. 	return 0;
  89. }
Success #stdin #stdout 0.94s 136716KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
115354012
https://ideone.com/ZZXwib
language:
C++14 (gcc 8.3)
created:
5 days 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!