VP 2023 CCPC 哈尔滨

第九届中国大学生程序设计竞赛 哈尔滨站（CCPC 2023 Harbin Site）
The 2nd Universal Cup. Stage 10: Harbin
Date 2025/10/30
(Up)Solved 6 / 13

A	B	C	D	E	F	G	H	I	J	K	L	M
	O		Ø			O			O		O	O

D - A Simple MST Problem

定义函数

$$
\omega(x) = \text{不同质因子个数}
$$

若在两个节点 $x,y$ 之间建边，则边权定义为：

$$
w(x,y) = \omega(\mathrm{lcm}(x,y))
$$

给出多个询问，每次给一个区间 $[l,r]$。
我们只能在该区间内的点之间建边，求最小生成树代价。

$T \le 50000$
$1 \le l_i \le r_i \le 10^6$
$\sum r_i \le 10^6$

首先 $w(x,y) = |P(x)\cup P(y)|$

考虑一个数论概念，定义 radical(x) = $\prod_{p\mid x} p$

同样 radical 的数，意味着，质因子集合相同。

首先考虑下，$[L, R]$ 内没有质数的情况，这意味着区间不是很大，可以直接跑 Prim。

接下来讨论 $[L, R]$ 内有质数的情况。

对于一个数 $x$，只需要考虑两种情况：

• 和同 radical 的数连边，边权 $\omega(x)$
• 和某质数连边，边权 $\omega(x) + 1$

并且不会有更优的情况

更进一步地，可以直接按 radical 分组，组内先做一下最小生成树，贡献 $(c - 1) \cdot \omega(radical)$，$c$ 为该组大小

然后考虑组和组之间如何连边：从小到大遍历，每个组连向包含它的最小祖先组

#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using namespace std;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while (48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
#define fi first
#define se second
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for (auto x : a) cout << x << " "; cout << "\n";
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; i++) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; i++) cerr << *i << " "; cerr << '\n'; }
template <class T> bool cmin(T &a, T b) { return (b < a) ? (a = b, true) : false; }
template <class T> bool cmax(T &a, T b) { return (a < b) ? (a = b, true) : false; }
using pii = pair<int, int>;
using tup = tuple<int, int, int>;
const int inf = 1e18;
const double eps = 1e-9;

struct Node {
    int cur, dis;
    bool friend operator < (Node a, Node b) {
        return a.dis > b.dis;
    }
};

std::vector<int> minp, primes;
vector<vector<int>> facs;
vector<int> w, rad;
void sieve(int n) {
    minp.assign(n + 1, 0), primes.clear();
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) minp[i] = i, primes.push_back(i);
        for (auto p : primes) {
            if (i * p > n) break;
            minp[i * p] = p;
            if (p == minp[i]) break;
        }
    }

    facs.assign(n + 1, {});
    for (auto p : primes) {
        for (int j = p; j <= n; j += p) {
            facs[j].eb(p);
        }
    }

    w.assign(n + 1, 0);
    rad.assign(n + 1, 1LL);
    for (int i = 1; i <= n; i++) {
        w[i] = facs[i].size();
        for (int t : facs[i]) rad[i] *= t;
    }
}

void solve() {
    int L = read(), R = read();
    if (*ranges::lower_bound(primes, L) <= R) {
        vector<int> vis(R + 1);
        int ans = 0;
        for (int i = L; i <= R; i++) {
            if (vis[rad[i]]) {
                ans += w[i];
            } else {
                vis[rad[i]] = 1;
            }
        }
        int f = 1;
        for (int i = 1; i <= R; i++) {
            if (!vis[i]) continue;

            if (w[i] <= 1 and f) {
                f = 0;
            } else {
                ans += w[i] + 1;
            }

            for (int j = 2 * i; j <= R; j += i) {
                if (vis[j]) ans += w[j], vis[j] = 0;
            }
        }
        cout << ans << '\n';
    } else {

        auto dis = [&](int u, int v) {
            int res = w[u];
            for (auto p : facs[v]) if (rad[u] % p != 0) res++;
            return res;
        };
        
        int ans = 0;

        priority_queue<Node> pq;
        for (int i = L + 1; i <= R; i++) {
            pq.ep(i, dis(L, i));
        }

        vector<int> vis(R + 1);
        vis[L] = 1;

        for (int i = 1; i < R - L + 1; i++) {
            while (vis[pq.top().cur]) pq.pop();
            auto [u, d] = pq.top(); pq.pop();

            ans += d;
            vis[u] = 1;

            for (int v = L; v <= R; v++) {
                if (vis[v]) continue;
                pq.ep(v, dis(u, v));
            }
        }
        cout << ans << '\n';
    }
}

signed main() {
    sieve(1000000);
    for (int T = read(); T--; solve());
    // solve();
    return 0;
}