fork download
copy 
  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair < int, int > ii;
  7.  
  8. const int N = 1e5 + 5;
  9. const int M = 1e7 + 5;
  10.  
  11. int n;
  12. int a[N], root[N], cnt[M], nxt[M];
  13. vector < ii > v;
  14.  
  15. int f(int x) {
  16.     if(x == root[x])
  17.         return x;
  18.     return root[x] = f(root[x]);
  19. }
  20.  
  21. int main() {
  22.  
  23.     scanf("%d", &n);
  24.  
  25.     for(int i = 1; i <= n; i++)
  26.         scanf("%d", a + i), root[i] = i;
  27.  
  28.     sort(a + 1, a + n + 1);
  29.     n = unique(a + 1, a + n + 1) - a - 1;
  30.  
  31.     for(int i = 1; i <= n; i++)
  32.         nxt[a[i]] = i;
  33.  
  34.     nxt[M - 1] = n + 1;
  35.     for(int i = M - 2; i >= 1; i--)
  36.         if(!nxt[i])
  37.             nxt[i] = nxt[i + 1];
  38.  
  39.     ll ans = 0;
  40.  
  41.     for(int i = n - 1; i >= 1; i--) {
  42.         for(int j = a[i]; j < M; j += a[i]) {
  43.             int k = nxt[j + (a[i] == j)];
  44.             if(k > n)
  45.                 break;
  46.             if(a[k] - j < a[i]) {
  47.                 cnt[a[k] - j]++;
  48.                 v.push_back({i, k});
  49.             }
  50.             else
  51.                 j = a[k] / a[i] * a[i] - a[i];
  52.         }
  53.     }
  54.  
  55.     for(int i = 1; i < M; i++)
  56.         cnt[i] += cnt[i - 1];
  57.  
  58.     auto res = v;
  59.  
  60.     for(auto x : v)
  61.         res[--cnt[a[x.second] % a[x.first]]] = x;
  62.  
  63.     for(auto x : res) {
  64.         if(f(x.first) == f(x.second))
  65.             continue;
  66.         ans += a[x.second] % a[x.first];
  67.         root[f(x.first)] = f(x.second);
  68.     }
  69.  
  70.     printf("%lld\n", ans);
  71.  
  72.     return 0;
  73. }
  74.  
  75.  
  76.  
Success #stdin #stdout 0.04s 82368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/iqBChI
language:
C++14 (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!