/*
weak weak we ak we akwea weak we
weak weak we ak weak weak we ak we
weakweak we ak wea ak we akwe
wea we ak we ak we akwe
wea we ak we ak we akwe
wea eak weak we ak we ak we
wea wea ak we ak weak we
we
we ak wea ak weak we
we ak wea weak wea eak we
we ak we ak wea wea we we
weak we ak we we we we
we we ak we we we we
we wea weak wea wea weak weak
weak wea akw weak weak
*/
//#define _GLIBCXX_DEBUG //is only used when couldn't find bug
using namespace std;
#pragma GCC optimize ("Ofast")
//headers
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <utility>
#include <bitset>
#include <set>
#include <string>
#include <stack>
#include <iomanip>
#include <map>
#include <memory.h>
#include <deque>
#include <time.h>
#include <assert.h>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
//defines
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<LL>> vvl;
#define pb push_back
#define F first
#define S second
#define mid (LB+RB)/2
#define mkp make_pair
//iterators
#define iter(x) x.begin(),x.end()
#define aiter(a,n) a,a+n
//loops
#define REP(n) for (int ___=n > 0 ? n : 0;___--;)
#define REP0(i,n) for (int i=0,___=n;i<___;++i)
#define REP1(i,n) for (int i=1,___=n;i<=___;++i)
#define MEM(e,val) memset (e,val,sizeof(e))
/*
every one is so dian except me
still too weak 咩噗
*/
//IO
#include <cstdio>
#include <iostream>
#include <fstream>
#define want_to_be_more_dian ios_base::sync_with_stdio(false),cin.tie(0);
//pbds
/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
//tree <pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update>;
*/
//constants
#include <climits>
const int maxn = 1e7+10,mod = 0;
const long long inf = 0;
const double eps = 0;
//workspace
bool app[maxn];
struct _edge{
int u,v;
int w;
bool operator<(_edge a){
return w < a.w;
}
_edge(int u,int v,int w): u(u), v(v), w(w){}
};
struct DSU{
int dsu[maxn];
void init(vector <int> &v){
for (auto &i:v) dsu[i] = i;
}
int query(int k){
return k == dsu[k] ? k : dsu[k] = query(dsu[k]);
}
void merge(int u,int v){
u = query(u); v = query(v);
dsu[v] = u;
}
}dsu;
inline void solve(){
int n;
cin >> n;
int mx = 1;
REP(n){
int x;
cin >> x;
app[x] = true;
mx = max(mx,x);
}
vector <int> vv;
vv.reserve(n);
REP1(i,mx) if (app[i]) vv.pb(i);
vector <_edge> edge;
edge.reserve(n*10);
for (auto &x:vv){
auto it = upper_bound(iter(vv),x);
if (it != vv.end() and *it - x < x) edge.pb(_edge(x, *it, *it - x));
for (int k=x+x;k<=mx;k+=x){
auto it = lower_bound(iter(vv),k);
if (it == vv.end()) break;
k = *it - *it % x;
edge.pb(_edge(x, *it, *it - k));
}
}
sort(iter(edge));
dsu.init(vv);
LL ans = 0;
int c = vv.size();
for (auto &[u,v,w]:edge){
if (dsu.query(u) != dsu.query(v)){
//cout << u << ' ' << v << '\n';
dsu.merge(u,v);
ans += w;
if (!--c) break;
}
}
cout << ans;
}
/*
5
9 12 13 21 23
*/
signed main(){
want_to_be_more_dian
//int t,i=1; for (int ;cin;)//use in multi-testcases and end in EOF problems
//int t,i=1; for (cin >> t;i<=t;++i)//use in multi-testcases problems
//cout << "Case #" << i << ": ",//use in Google, FB competitions
solve();//always used
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
7116 KB |
Output is correct |
| 2 |
Correct |
32 ms |
6400 KB |
Output is correct |
| 3 |
Correct |
12 ms |
7756 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
460 KB |
Output is correct |
| 2 |
Correct |
14 ms |
2024 KB |
Output is correct |
| 3 |
Correct |
12 ms |
7708 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
7632 KB |
Output is correct |
| 2 |
Correct |
10 ms |
3916 KB |
Output is correct |
| 3 |
Correct |
12 ms |
7620 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
173 ms |
25056 KB |
Output is correct |
| 2 |
Correct |
549 ms |
89048 KB |
Output is correct |
| 3 |
Correct |
202 ms |
25004 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
6872 KB |
Output is correct |
| 2 |
Correct |
285 ms |
48360 KB |
Output is correct |
| 3 |
Correct |
154 ms |
23108 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
365 ms |
48624 KB |
Output is correct |
| 2 |
Correct |
685 ms |
95528 KB |
Output is correct |
| 3 |
Correct |
184 ms |
25080 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
48 ms |
5500 KB |
Output is correct |
| 2 |
Correct |
669 ms |
95580 KB |
Output is correct |
| 3 |
Correct |
178 ms |
25104 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
279 ms |
63764 KB |
Output is correct |
| 2 |
Correct |
3181 ms |
386272 KB |
Output is correct |
| 3 |
Correct |
307 ms |
66832 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
249 ms |
63756 KB |
Output is correct |
| 2 |
Correct |
4565 ms |
420972 KB |
Output is correct |
| 3 |
Correct |
315 ms |
72424 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
61 ms |
46352 KB |
Output is correct |
| 2 |
Correct |
4775 ms |
412080 KB |
Output is correct |
| 3 |
Correct |
218 ms |
25124 KB |
Output is correct |
