Guest User

140

a guest
Feb 4th, 2017
132
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define fs first
  4. #define sc second
  5. #define mp make_pair
  6. #define pb emplace_back
  7. #define sz(s) ((int) s.size ())
  8. #define all(s) s.begin (), s.end ()
  9.  
  10. using namespace std;
  11.  
  12. typedef long long ll;
  13. typedef pair<int, int> ii;
  14. typedef unsigned long long ull;
  15.  
  16. const ll linf = (ll) 1e18;
  17.  
  18. const int pw = 997;
  19. const int N = 100009;
  20. const int M = 10000000;
  21. const int inf = (int) 1e9;
  22. const int mod = (int) 1e9 + 7;
  23.  
  24. const double eps = 1e-10;
  25. const double pi = 3.1415926535897932384626433832795;
  26.  
  27. int a[N];
  28.  
  29. int p[M + 9];
  30. int r[M + 9];
  31.  
  32. bool e[M + 9];
  33.  
  34. int get (int v) {
  35.         return v == p[v] ? v : p[v] = get (p[v]);
  36. }
  37. bool unite (int a, int b) {
  38.         a = get (a);
  39.         b = get (b);
  40.         if (a != b) {
  41.                 if (r[a] < r[b]) {
  42.                         swap (a, b);
  43.                 }
  44.                 p[b] = a;
  45.                 if (r[a] == r[b]) {
  46.                         r[a]++;
  47.                 }
  48.                 return 1;
  49.         }
  50.         return 0;
  51. }
  52. inline void prepare () {
  53.  
  54. }
  55. inline void solve () {
  56.         int n; scanf ("%d", &n);
  57.         int mn = +M;
  58.         int mx = -M;
  59.         for (int i = 0; i < n; i++) {
  60.                 scanf ("%d", &a[i]);
  61.                 e[a[i]] = 1;
  62.                 p[a[i]] = a[i];
  63.                 mn = min (mn, a[i]);
  64.                 mx = max (mx, a[i]);
  65.         }
  66.         sort (a, a + n);
  67.         n = unique (a, a + n) - a;
  68.         if (n == 1) {
  69.                 puts ("0");
  70.                 return;
  71.         }
  72.         if (n <= 10000) {
  73.                 vector<bool> used (n);
  74.                 vector<int> min_e (n, inf), sel_e (n, -1);
  75.                 min_e[0] = 0;
  76.                 ll ans = 0;
  77.                 for (int i = 0; i < n; i++) {
  78.                         int v = -1;
  79.                         for (int j = 0; j < n; j++) {
  80.                                 if (!used[j] && (v == -1 || min_e[j] < min_e[v])) {
  81.                                         v = j;
  82.                                 }
  83.                         }
  84.                         used[v] = true;
  85.                         ans += min_e[v];
  86.                         for (int to = 0; to < n; to++) {
  87.                                 int now = min (a[v] % a[to], a[to] % a[v]);
  88.                                 if (now < min_e[to]) {
  89.                                         min_e[to] = now;
  90.                                         sel_e[to] = v;
  91.                                 }
  92.                         }
  93.                 }
  94.                 printf ("%lld", ans);
  95.                 return;
  96.         }
  97.         ll ans = 0;
  98.         int cmp = n;
  99.         for (int r = 0; r < mn; r++) {
  100.                 for (int i = 0; i < n; i++) {
  101.                         for (int j = a[i]; j <= mx; j += a[i]) {
  102.                                 if (e[j + r]) {
  103.                                         bool u = unite (a[i], j + r);
  104.                                         if (u) {
  105.                                                 cmp--;
  106.                                                 ans += r;
  107.                                                 if (cmp == 1) {
  108.                                                         printf ("%lld", ans);
  109.                                                         return;
  110.                                                 }
  111.                                         }
  112.                                 }
  113.                         }
  114.                 }
  115.         }
  116. }
  117. int main () {
  118.         #ifdef FSTREAM
  119.                 #define name ""
  120.                 freopen (name".in", "r", stdin);
  121.                 freopen (name".out", "w", stdout);
  122.         #endif // FSTREAM
  123.         int tests = 1;
  124.         prepare ();
  125.     while (tests--) {
  126.                 solve ();
  127.         }
  128. }
RAW Paste Data