最短距离 题解

题目分析

本题给了一张含有 $N = 10^{18}$ 个结点的完全图，任意两点之间都有一条边。边的权值只有两种情况：

• 两点编号互质，边权为 $p$；
• 两点编号不互质，边权为 $q$。

现在有 $n$ 组询问，每次给定 $a,b$，求它们之间的最短距离。

直接建图是不可能的，$N$ 太大。我们需要深入分析图的性质，找出最短路径的规律。

解题思路

核心观察：任意两点间最短距离不超过 2

对于任意两个结点 $u,v$，它们之间的距离最多为 $2$。也就是说，最短路径要么是直接相连，要么只经过一个中间结点。为什么？

因为我们可以人为构造一个中间结点 $w$，使得：

• $u$ 与 $w$ 的连边，以及 $v$ 与 $w$ 的连边，都符合我们想要的边权类型；
• 并且 $w$ 在编号范围内（$\le 10^{18}$）。

因此，两点间的最短距离只可能是以下三种情况之一：

1. 直接边：如果 $\gcd(u,v)=1$，距离为 $p$；否则距离为 $q$。
2. 走两步互质边：$u \to w \to v$，两条边都是 $p$，总距离 $2p$。
3. 走两步不互质边：$u \to w \to v$，两条边都是 $q$，总距离 $2q$。

为什么不考虑“一互质、一不互质”的混合情况 $p+q$ 呢？因为 $2p$ 和 $2q$ 中较小的那个一定不大于 $p+q$（若 $p\le q$ 则 $2p \le p+q$；若 $p>q$ 则 $2q \le p+q$），所以混合路径永远不会比纯 $2p$ 或纯 $2q$ 更优。

因此，答案就是上述三种情况中的最小值。问题的关键变成：是否总能找到合法的中间点 $w$，使得上述两种情况（$2p$ 与 $2q$）都能被构造出来？

构造中间点 $w$ 的可行性

构造 $2p$ 路径（两边都互质）
我们需要一个 $w$，满足 $\gcd(u,w)=1$ 且 $\gcd(v,w)=1$。
因为 $u,v \le 10^9$，而结点编号最大到 $10^{18}$，我们可以选取一个大于 $\max(u,v)$ 的质数作为 $w$。这个质数不会与 $u$ 或 $v$ 的任何质因子相同，因此与二者均互质。由于 $10^9$ 到 $10^{18}$ 之间存在大量的质数，这样的 $w$ 一定存在。所以 $2p$ 路径对任意 $u,v$ 都可行。

构造 $2q$ 路径（两边都不互质）
我们需要一个 $w$，满足 $\gcd (u,w)>1$ 且 $\gcd (v,w)>1$。
可以令 $w = u \times v$。显然 $\gcd (u,w)=u>1$，$\gcd (v,w)=v>1$。当 $u,v>1$ 时，$w$ 与 $u,v$ 均不等，且由于 $u,v \le 10^9$，$w \le 10^{18}$，恰好在编号范围内。所以 $2q$ 路径对任意 $>1$ 的 $u,v$ 也总是可行的。

特殊情况：包含 1

若 $u=1$ 或 $v=1$，则与 $1$ 的边只能是互质边（因为 $1$ 与任何数互质）。此时：

• 直接边距离为 $p$；
• 无法走 $2q$ 路径，因为 $1$ 无法与任何结点不互质；
• $2p$ 路径虽然存在，但 $2p \ge p$，不会更优。

因此当有结点为 $1$ 时，答案直接就是 $p$（除非 $u=v$，答案为 $0$）。

算法说明

对于每组询问 $(a,b)$：

1. 若 $a = b$，输出 $0$。
2. 若 $a=1$ 或 $b=1$，输出 $p$。
3. 否则：
   • 初始化答案 $ans = \min(2p, 2q)$。
   • 若 $\gcd(a,b) = 1$，则可以用直接互质边：$ans = \min(ans, p)$。
   • 若 $\gcd (a,b)>1$，则可以用直接不互质边：$ans = \min(ans, q)$。
   • 输出 $ans$。

时间复杂度分析

• 每组询问需要计算一次 $\gcd$，复杂度 $O(\log \min(a,b))$。
• 共有 $n \le 10^4$ 组询问，总复杂度 $O(n \log 10^9)$，在 $1000\text{ms}$ 内完全可以通过。

空间复杂度 $O(1)$，仅需几个变量。

---

参考代码

下面是基于 C++ 的参考实现，使用了 long long 避免可能的整数溢出，并加入了详细注释。

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4
5typedef long long ll;
6
7ll gcd(ll a, ll b) {
8    while (b) {
9        ll t = a % b;
10        a = b;
11        b = t;
12    }
13    return a;
14}
15
16int main() {
17    int n;
18    ll p, q;
19    scanf("%d%lld%lld", &n, &p, &q);
20
21    while (n--) {
22        ll a, b;
23        scanf("%lld%lld", &a, &b);
24
25        ll ans;
26        if (a == b) {
27            ans = 0;                     // 同一个结点，距离为 0
28        } else if (a == 1 || b == 1) {
29            ans = p;                     // 有 1 只能走互质边
30        } else {
31            ans = min(p * 2, q * 2);    // 两步路径的最小代价
32            if (gcd(a, b) == 1) {
33                ans = min(ans, p);       // 直接互质边
34            } else {
35                ans = min(ans, q);       // 直接不互质边
36            }
37        }
38        printf("%lld\n", ans);
39    }
40    return 0;
41}

代码说明

• 变量类型：将 $p,q,a,b$ 均定义为 long long，防止计算 p*2 或 q*2 时在极端数据下溢出 int。
• gcd 函数：利用辗转相除法计算最大公约数。
• 逻辑分支：
  • 同点答案为 $0$。
  • 遇 $1$ 答案为 $p$（因为 $1$ 与任何数互质，且两步互质边不会更短）。
  • 其他情况先取 $2p$ 和 $2q$ 的最小值作为候选，再根据是否互质考虑直接边的长度。
• 输出每行对应一组询问的答案。

这样，我们就用 $O(1)$ 的额外空间和极快的速度解决了这道看似复杂的最短路问题。