#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
struct triple
{
int u,v,w;
};
bool operator < (triple a,triple b)
{
return a.w<b.w;
}
const int nmax=1e5+69;
int n,mx=0;
vector<pii> p;
vector<triple> edge;
bool cnt[1000001];
//vector<triple> save[1000001];
void input()
{
cin >> n;
FOR(i,1,n)
{
int x; cin >> x;
if(!cnt[x]) p.push_back({x,i});
cnt[x]=true;
mx=max(mx,x);
}
}
//void counting_sort()
//{
// FORD(i,edge) save[i.w].push_back(i);
// edge.clear();
// FOR(i,0,1e6) FORD(j,save[i]) edge.push_back(j);
//}
struct DSU
{
vector<int> par;
DSU() {}
void init(int n)
{
par.resize(n+5,0);
FOR(i,1,n) par[i]=i;
}
int find(int v)
{
if(v==par[v]) return v;
return par[v]=find(par[v]);
}
bool joint(int u,int v)
{
u=find(u);
v=find(v);
if(u!=v)
{
par[v]=u;
return true;
}
return false;
}
};
DSU dsu;
void solve()
{
dsu.init(n);
sort(p.begin(),p.end());
FORD(i,p)
{
for(int j=i.fi;j<=mx;j+=i.fi)
{
auto it=lower_bound(p.begin(),p.end(),make_pair(j,1ll*0));
if(it!=p.end()) edge.push_back({i.se,(*it).se,(*it).fi%i.fi});
}
}
sort(edge.begin(),edge.end());
// counting_sort();
int ans=0;
FORD(i,edge) ans+=dsu.joint(i.u,i.v)*i.w;
cout << ans;
}
signed main()
{
//freopen(".inp", "r", stdin);
//freopen(".out", "w", stdout);
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
input();
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |