fork(3) download
  1. //84104971101048411497 - Can you guess what does this mean?
  2. using namespace std;
  3. #include <bits/stdc++.h>
  4. #define mapii map<int, int>
  5. #define debug(a) cout << #a << ": " << a << endl
  6. #define debuga1(a, l, r) fto(i, l, r) cout << a[i] << " "; cout << endl
  7. #define fdto(i, r, l) for(int i = (r); i >= (l); --i)
  8. #define fto(i, l, r) for(int i = (l); i <= (r); ++i)
  9. #define ftoa(i, l, r, a) for(int i = (l); i <= (r); i += a)
  10. #define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); it++)
  11. #define forrit(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); rit++)
  12. #define ii pair<int, int>
  13. #define iii pair<int, ii>
  14. #define ff first
  15. #define ss second
  16. #define mp make_pair
  17. #define pb push_back
  18. #define ll long long
  19. #define sizeX 10000005
  20. #define next abcxyz
  21. #define sz(a) (int)(a.size())
  22.  
  23. template <class T>
  24. T min(T a, T b, T c) {
  25. return min(a, min(b, c));
  26. }
  27.  
  28. template <class T>
  29. T max(T a, T b, T c) {
  30. return max(a, max(b, c));
  31. }
  32.  
  33. template <class T>
  34. void read(vector<T> &v) {
  35. T x;
  36. cin >> x;
  37. v.pb(x);
  38. }
  39.  
  40. struct edge {
  41. int u, v, c;
  42. edge() {}
  43. edge(int u, int v, int c): u(u), v(v), c(c) {}
  44. bool inline operator < (const edge &o) const {
  45. return c < o.c;
  46. }
  47. };
  48.  
  49. int n, next[sizeX];
  50. bool avail[sizeX];
  51. vector<int> a;
  52. vector<edge> e;
  53.  
  54. class UFDS {
  55. private: int n; vector<int> pset;
  56. public:
  57. UFDS(int n) {
  58. pset.resize(n);
  59. fto(i, 0, n-1) pset[i] = i;
  60. }
  61. int findSet(int u) {
  62. return (pset[u] == u) ? u : pset[u] = findSet(pset[u]);
  63. }
  64. bool unionSet(int u, int v) {
  65. int p = findSet(u), q = findSet(v);
  66. if (p == q) return false;
  67. pset[p] = q;
  68. return true;
  69. }
  70. };
  71.  
  72. int main () {
  73. #ifndef ONLINE_JUDGE
  74. freopen("input.txt", "r", stdin);
  75. //freopen("output.txt", "w", stdout);
  76. #endif // ONLINE_JUDGE
  77.  
  78. scanf("%d", &n);
  79. int maxX = 0;
  80. fto(i, 0, n-1) {
  81. int x; scanf("%d", &x);
  82. avail[x] = true;
  83. maxX = max(maxX, x);
  84. }
  85.  
  86. next[maxX+1] = -1;
  87. fdto(x, maxX, 1) {
  88. if (avail[x]) {
  89. next[x] = sz(a);
  90. a.pb(x);
  91. } else next[x] = next[x+1];
  92. }
  93.  
  94. memset(avail, false, sizeof avail);
  95. fto(i, 0, sz(a)-1) {
  96. vector<int> save;
  97. ftoa(k, a[i], maxX, a[i]) {
  98. int j = next[k + (k == a[i])];
  99. if (j >= 0 && !avail[j]) {
  100. e.pb(edge(i, j, a[j]%a[i]));
  101. avail[j] = true; save.pb(j);
  102. }
  103. }
  104. forit(it, save) avail[*it] = false;
  105. }
  106.  
  107. sort(e.begin(), e.end());
  108.  
  109. UFDS s(a.size());
  110. int ans = 0;
  111. forit(it, e) {
  112. if (s.unionSet(it->u, it->v)) ans += it->c;
  113. }
  114.  
  115. printf("%d", ans);
  116.  
  117. return 0;
  118. }
  119.  
  120.  
Success #stdin #stdout 0s 52304KB
stdin
4
2
6
3
11
stdout
1