/*
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];
vector <pii> edge[maxn];
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);
for (auto &x:vv){
auto it = upper_bound(iter(vv),x);
if (it != vv.end() and *it - x < x) edge[*it - x].pb(mkp(x, *it));
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[*it - k].pb(mkp(x, *it));
}
}
dsu.init(vv);
LL ans = 0;
int c = vv.size();
REP0(w,mx) for (auto &[u,v]:edge[w]){
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 |
171 ms |
242020 KB |
Output is correct |
| 2 |
Correct |
182 ms |
241372 KB |
Output is correct |
| 3 |
Correct |
174 ms |
242484 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
142 ms |
235296 KB |
Output is correct |
| 2 |
Correct |
175 ms |
236656 KB |
Output is correct |
| 3 |
Correct |
174 ms |
242500 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
182 ms |
242628 KB |
Output is correct |
| 2 |
Correct |
208 ms |
238728 KB |
Output is correct |
| 3 |
Correct |
175 ms |
242532 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
260 ms |
249604 KB |
Output is correct |
| 2 |
Correct |
523 ms |
276808 KB |
Output is correct |
| 3 |
Correct |
292 ms |
254976 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
154 ms |
241668 KB |
Output is correct |
| 2 |
Correct |
297 ms |
261044 KB |
Output is correct |
| 3 |
Correct |
267 ms |
247392 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
400 ms |
261124 KB |
Output is correct |
| 2 |
Correct |
630 ms |
287936 KB |
Output is correct |
| 3 |
Correct |
281 ms |
253244 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
173 ms |
239452 KB |
Output is correct |
| 2 |
Correct |
557 ms |
286012 KB |
Output is correct |
| 3 |
Correct |
280 ms |
253144 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
364 ms |
296404 KB |
Output is correct |
| 2 |
Correct |
2261 ms |
492624 KB |
Output is correct |
| 3 |
Correct |
406 ms |
298708 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
402 ms |
296184 KB |
Output is correct |
| 2 |
Correct |
3105 ms |
582296 KB |
Output is correct |
| 3 |
Correct |
405 ms |
302628 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
216 ms |
281192 KB |
Output is correct |
| 2 |
Correct |
2861 ms |
570872 KB |
Output is correct |
| 3 |
Correct |
283 ms |
254776 KB |
Output is correct |
