fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
  5. #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
  6. #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
  7.  
  8. #define MAX 100005
  9. int parent[MAX];
  10. int n, Max = 0;
  11.  
  12. struct menkh {
  13.     int u, v, w;
  14. };
  15.  
  16. vector<menkh> adj;
  17.  
  18. int root(int v) {
  19.     return v == parent[v] ? v : parent[v] = root(parent[v]);
  20. }
  21.  
  22. bool unite(int u, int v) {
  23.     u = root(u), v = root(v); 
  24.     if (u == v) return false;
  25.     parent[v] = u;
  26.     return true;
  27. }
  28.  
  29. void solve() {
  30.     scanf("%d", &n); 
  31.     vector<int> p(n + 1);
  32.     FOR(i, 1, n) {
  33.         scanf("%d", &p[i]); 
  34.         Max = max(p[i], Max);
  35.     }
  36.  
  37.     sort(p.begin() + 1, p.end());
  38.     p.erase(unique(p.begin() + 1, p.end()), p.end());
  39.     n = p.size() - 1;
  40.     FOR(i, 1, n) parent[i] = i;
  41.  
  42.     FOR(i, 1, n) {
  43.         for (int k = 1; k * p[i] <= Max; k++) {
  44.             int v = lower_bound(p.begin() + 1, p.begin() + n + 1, k * p[i]) - p.begin();
  45.             if (v == n + 1) break; 
  46.             if (p[v] <= (k + 1) * p[i]) adj.push_back({i, v, p[v] % p[i]});
  47.         }
  48.     }
  49.  
  50.     sort(adj.begin(), adj.end(), [](menkh A, menkh B) {
  51.         return A.w < B.w;
  52.     });
  53.  
  54.     long long answer = 0;
  55.     REP(i, (int)adj.size()) {
  56.         if (unite(adj[i].u, adj[i].v)) answer += adj[i].w;
  57.     }
  58.  
  59.     printf("%lld\n", answer);
  60. }
  61.  
  62. int main() {
  63.     solve();
  64. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
3
4
9
15
stdout
copy 
4
https://ideone.com/hpTBa9
language:
C++14 (gcc 8.3)
created:
2 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!