Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Those who cannot remember the past are
- // condemned to repeat it (use DP -_-)
- // - George Santayana
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define ll long long
- #define ull unsigned long long
- #define MOD 1000000007
- #define PI acos(-1)
- #define ceil(a, b) (((a) / (b)) + ((a) % (b) ? 1 : 0))
- #define imin INT_MIN
- #define imax INT_MAX
- #define llmax LLONG_MAX
- #define llmin LLONG_MIN
- #define inf 2000000000
- #define nl '\n'
- #define ppcnt __builtin_popcount
- #define ppcntll __builtin_popcountll
- #define clz __builtin_clz
- #define clzll __builtin_clzll
- #define ctz __builtin_ctz
- #define ctzll __builtin_ctzll
- #define modulo(a, b, mod) ((((a) % (mod)) + ((b) % (mod))) % (mod))
- #define cnte(v, x) count(all(v), (x))
- #define mine(v) min_element(all(v))
- #define maxe(v) max_element(all(v))
- #define updmin(a, b) a = min(a, b)
- #define updmax(a, b) a = max(a, b)
- #define findmod(x, m) x = ((x) % (m) + (m)) % m
- #define getmod(x, m) ((x) % (m) + (m)) % (m)
- #define debug(x) cout << "x: " << (x) << nl;
- #define debug2(x, y) cout << "x: " << (x) << " y: " << y << nl;
- #define ordered_set tree<pair<int, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>
- #define ordered_map tree<int, int, less<>, rb_tree_tag, tree_order_statistics_node_update>
- //vector<int> dx = {0, 0, 1, -1, 1, 1, -1, -1}, dy = {1, -1, 0, 0, 1, -1, 1, -1};
- vector<int> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
- template<typename T = int>
- istream &operator>>(istream &in, vector<pair<int, int>> &v) {
- for (auto &[x, y]: v) in >> x >> y;
- return in;
- }
- template<typename T = int>
- istream &operator>>(istream &in, vector<T> &v) {
- for (T &i: v) in >> i;
- return in;
- }
- template<typename T = int>
- ostream &operator<<(ostream &out, const vector<T> &v) {
- for (const T &x: v)
- out << x << ' ';
- return out;
- }
- template<typename T = pair<int, int>>
- ostream &operator<<(ostream &out, const vector<pair<int, int>> &v) {
- for (auto &[x, y]: v) {
- out << x << ' ' << y << nl;
- }
- return out;
- }
- void Start_Crushing() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- }
- struct dsu {
- vector<int> p, rank;
- explicit dsu(int size) {
- p.resize(size + 1);
- rank.resize(size + 1);
- iota(all(p), 0);
- }
- int get(int x) {
- return p[x] = x == p[x] ? x : get(p[x]);
- }
- void join(int u, int v) {
- u = get(u), v = get(v);
- if (u == v)
- return;
- if (rank[u] == rank[v])
- rank[u]++;
- if (rank[u] > rank[v])
- p[v] = u;
- else
- p[u] = v;
- }
- };
- vector<vector<int>> factors;
- void build(int limit){
- factors.assign(limit + 5, vector<int>());
- for(int i = 1; i <= limit; i++){
- for(int j = i; j <= limit; j += i)
- factors[j].emplace_back(i);
- }
- }
- void solve(){
- int n; cin >> n;
- dsu d(n);
- vector<int> vec;
- int mx = imin;
- for(int i = 0; i < n; i++){
- int x; cin >> x;
- vec.emplace_back(x);
- updmax(mx, x);
- }
- vector<vector<int>> adj(mx + 5, vector<int>());
- for(int i = 0; i < n; i++){
- for(auto& factor : factors[vec[i]])
- adj[factor].emplace_back(i);
- }
- ll ans = 0;
- for(int i = (int)adj.size() - 1; i >= 1; i--){
- for(int j = 1; j < adj[i].size(); j++){
- int u = adj[i][j], v = adj[i][j - 1];
- if(d.get(u) != d.get(v)){
- d.join(u, v);
- ans += i;
- }
- }
- }
- cout << ans;
- }
- void set_file(string &file_name) {
- freopen((file_name + ".in").c_str(), "r", stdin);
- // freopen((file_name + ".out").c_str(), "w", stdout);
- }
- int main() {
- Start_Crushing();
- string file_name = "dream";
- set_file(file_name);
- build(100000);
- int t = 1;
- /*Multiple test cases?*/ cin >> t;
- // while (t--) {
- // solve();
- // if (!t)
- // break;
- // cout << nl;
- // }
- for(int tc = 1; tc <= t; tc++){
- cout << "Case " << tc << ": ";
- solve();
- // if(tc != t)
- cout << nl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement