# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1124434 | codexistent | Sirni (COCI17_sirni) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 100005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
ll n, r = 0, p[MAXN], sz[MAXN];
vector<ll> v;
vector<pair<ll, pair<ll, ll>>> e;
void compress(){
set<ll> s(begin(v), end(v));
v.assign(begin(s), end(s));
}
ll find(ll x){
return (x == p[x]) ? x : (p[x] = find(p[x]));
}
bool onion(ll a, ll b){
a = find(a), b= find(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
p[a] = p[b] = a;
return true;
}
int main(){
cin >> n;
FOR(i, 1, n) {
ll x; cin >> x;
v.push_back(x);
}
compress();
n = v.size();
FOR(i, 1, n - 1) e.push_back({v[i] % v[i - 1], {i - 1, i}});
FOR(i, 0, n - 1){
for(ll j = v[i]; j <= MAXL; ){
ll lo = i + 1, hi = n;
while(lo < hi){
ll md = (lo + hi) / 2;
if(md == n || j <= v[md]){
hi = md;
}else{
lo = md + 1;
}
}
if(hi == n) break;
e.push_back({v[lo] % v[i], {lo, i}});
j = v[lo] / v[i] * v[i] + v[i];
}
}
FOR(i, 0, n - 1) p[i] = i, sz[i] = 1;
for(auto ei : e){
r += onion(ei.second.first, ei.second.second) * ei.first;
}
cout << r << endl;
}