#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll int
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll N = 1e5 + 5, MAX = 7e5 + 5;
struct Dsu
{
ll n, ans;
vector<ll> dsu;
Dsu(ll sz = 1)
{
n = sz;
ans = n;
dsu.resize(n + 1, 0);
init();
}
void init()
{
for (ll i = 0; i <= n; i++)
dsu[i] = -1;
}
bool Union(ll x, ll y)
{
x = repr(x), y = repr(y);
if (x == y)
return false;
if (dsu[x] < dsu[y])
swap(x, y);
ans--;
dsu[y] += dsu[x];
dsu[x] = y;
return true;
}
ll repr(ll x)
{
if (dsu[x] < 0)
return x;
return dsu[x] = repr(dsu[x]);
}
ll query()
{
return ans;
}
ll size(ll x)
{
return -dsu[repr(x)];
}
};
ll freq[MAX], ind[MAX];
vector<ll> consider[MAX];
vector<pair<ll, ll>> e[MAX];
ll best[N];
ll f(ll x, ll y)
{
return min(x % y, y % x);
}
void solve()
{
ll n;
cin >> n;
ll p[n];
for (ll &i : p) cin >> i;
long long ans = 0;
{
set<ll> s;
for (ll i : p) s.insert(i);
n = 0;
for (ll i : s) p[n++] = i;
}
for (ll i = 0; i < n; i++)
for (ll j = p[i]; j <= p[n - 1]; j += p[i])
Dsu dsu(n);
for (ll i = 0; i < n - 1; i++) e[f(p[i], p[i + 1])].push_back(make_pair(i, i + 1));
for (ll i = 0; i < n; i++)
for (ll w = p[i]; w <= p[n - 1]; w += p[i])
{
ll pos = lower_bound(p, p + n, w) - p;
if (pos < n)
for (ll i : consider[w]) if (p[pos] < w + p[i]) e[p[pos] - w].push_back(make_pair(pos, i));
consider[w].clear();
}
// for (ll i = 0; i < n; i++) for (ll j = 0; j < n; j++) e[f(p[i], p[j])].push_back(make_pair(i, j));
for (ll i = 0; i <= p[n - 1]; i++) for (auto [a, b] : e[i]) ans += dsu.Union(a, b) * i;
cout << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t = 1;
// precomp();
// cin >> t;
for (ll cs = 1; cs <= t; cs++)
solve();
// cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}
Compilation message
sirni.cpp: In function 'void solve()':
sirni.cpp:89:72: error: 'dsu' was not declared in this scope; did you mean 'Dsu'?
89 | for (ll i = 0; i <= p[n - 1]; i++) for (auto [a, b] : e[i]) ans += dsu.Union(a, b) * i;
| ^~~
| Dsu
