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