#include<bits/stdc++.h>
#define taskname "E"
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
int n;
namespace sub1{
void solve(){
vector<int>a(n);
for(int& x : a){
cin >> x;
}
vector<int>p(n);
iota(p.begin(), p.end(), 0);
auto find_set = [&] (int u){
while(u != p[u]){
u = p[u] = p[p[u]];
}
return u;
};
auto merge = [&] (int u, int v){
if((u = find_set(u)) != (v = find_set(v))){
p[u] = v;
return true;
}
return false;
};
vector<pair<int, pair<int, int>>>edge;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
edge.emplace_back(make_pair(min(a[i] % a[j], a[j] % a[i]), make_pair(i, j)));
}
}
sort(edge.begin(), edge.end());
ll ans = 0;
for(auto& [w, e] : edge){
if(merge(e.first, e.second)){
ans += w;
}
}
cout << ans;
}
}
namespace sub23{
const int LIM = 1e7 + 5;
int cnt[LIM], nxt[LIM], p[LIM];
vector<pair<int, int>>W[LIM >> 1];
int find_set(int u){
while(u != p[u]){
u = p[u] = p[p[u]];
}
return u;
}
bool merge(int u, int v){
if((u = find_set(u)) != (v = find_set(v))){
p[u] = v;
return true;
}
return false;
}
void solve(){
memset(cnt, 0, sizeof(cnt));
for(int i = 0; i < n; i++){
int x;
cin >> x;
cnt[x]++;
}
nxt[LIM - 1] = -1;
for(int i = LIM - 2; i > 0; i--){
nxt[i] = (cnt[i] > 0 ? i : nxt[i + 1]);
}
ll ans = 0;
for(int i = 1; nxt[i + 1] != -1; i++){
if(cnt[i] > 0){
int pre = nxt[i + 1];
W[pre % i].emplace_back(pre, i);
for(int j = i << 1; j < LIM && nxt[j] != -1; j += i){
if(nxt[j] != pre){
W[(pre = nxt[j]) % i].emplace_back(pre, i);
}
}
}
}
iota(p, p + LIM, 0);
for(int i = 0; i < (LIM >> 1); i++){
for(auto& [u, v] : W[i]){
if(merge(u, v)){
ans += i;
}
}
}
cout << ans;
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n;
if(n <= 1000){
sub1::solve();
}
else{
sub23::solve();
}
}
Compilation message (stderr)
sirni.cpp: In function 'int main()':
sirni.cpp:102:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |