洛谷 P4616 分析（别看）

科技起源的小号1

2026-09-09 20:07:04

发布于：天津

1阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：
有 $n$ 个城市，一些科学家
允许：
修路工程要持续 $m$ 天，第 $i$ 天将会将所有 $(u,v)$ 的一对科学家使得 $gcd(u,v)=m-i+1$ 连接起来
给出若干询问，求当前询问的这对科学家 $(a,b)$ 第几天才能被连接起来

1.3 题目数据范围与猜测

$1 \le n,q \le 10^5\longrightarrow O((n + q)~log~n)$

1.4 一句话概括题意

有一张初始只有若干点的图
对于每天将会对所有 $gcd(u,v)=m-i+1$ 的一对科学家 $(u,v)$ 之间建一条无向边，边权为 $i$
每次询问求 $(a,b)$ 这对科学家之间路径的边权最大值

2 题目破题推导

2.1 第一步：数学性质

我们知道第 $i$ 天会修好的路就是 $m-i+1$
那么能连接的两端一定保证 $gcd(a,b)=m-i+1$ ，所以每次对于连通的a和b，一定都是 $a=m-i+1,b=x(a)$
为什么这样就一定能保证连通？因为任意一对 $(a,b)$ 使得 $gcd(a,b)=m-i+1$ 都能通过 $a\rightarrow m-i+1\rightarrow b$ 连通

2.2 第二步：模型转换

因为本质上这是一张完全图（因为任意两条边都一定会有 $\ge1$ 条边相连——在 $i=m$ 时）
所以选出其中需要的 $n-1$ 条边就可以确保连通
那么把“ $n-1$ ”条边转化为一棵连通的树
树上求两点之间路径边权最大值就很好奇了

3 模型匹配

通过gcd建边+MST建图+LCA求最大值

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = 18;
int n, m, q;
vector<pair<int,int>> tree[N];
int fa[N];
void init_fa(){
    for (int i = 1;i <= n;i++){
        fa[i] = i;
    }
}
int find(int x){
    if (fa[x] != x){
        fa[x] = find(fa[x]);
    }
    return fa[x];
}
int dep[N], f[N][M], mx[N][M];
void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;
    for (pair<int, int> now : tree[u]) {
    	int v = now.first;
    	int w = now.second;
        if (v == fa) continue;
        mx[v][0] = w;
        dfs(v, u);
    }
}
void init() { 
	for (int j = 1;j < M;j++){
        for (int i = 1;i <= n;i++){
            f[i][j] = f[f[i][j - 1]][j - 1];
            mx[i][j] = max(mx[i][j - 1], mx[f[i][j - 1]][j - 1]);
        }
    }
}
int query(int u, int v) {
    int ans = 0;
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int j = 0; j < M; j++)
        if (diff & (1 << j)) {
            ans = max(ans, mx[u][j]);
            u = f[u][j];
        }
    if (u == v) return ans;
    for (int j = M - 1; j >= 0; j--) {
        if (f[u][j] != f[v][j]) {
            ans = max(ans, mx[u][j]);
            ans = max(ans, mx[v][j]);
            u = f[u][j];
            v = f[v][j];
        }
    }
    ans = max(ans, mx[u][0]);
    ans = max(ans, mx[v][0]);
    return ans;
}

int main() {
    
    cin >> n >> m >> q;
    init_fa();
    int cnt = 0;
    for (int i = 1; i <= m && cnt < n - 1; i++) {
        int k = m - i + 1;
        for (int j = k * 2; j <= n; j += k) {
            int a = find(k), b = find(j);
            if (a != b) {
                fa[a] = b;
                tree[k].push_back({j, i});
                tree[j].push_back({k, i});
                cnt++;
            }
        }
    }
    dfs(1, 0);
    init();
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << query(a, b) << endl;
    }
    return 0;
}