GESP 题解库 / 8 级题解 / [GESP202509 八级] 最短距离 · 第 6 / 24 题
GESP202509 八级 · P14079 · 中等

完全图上的最短距离

N = 10¹⁸ 的完全图,任意两点之间最多只需要走两条边:在 0 / p / q / 2p / 2q / p+q 里挑可行者取最小值。

🔢
N = 10¹⁸
结点数(完全图)
❓
n ≤ 10⁴
询问条数
⚡
O(n log a)
每次询问几次 gcd
🎯
最短路最多 2 条边
核心结论
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定正整数 p、q 以及常数 N = 10¹⁸。构建一张包含 N 个结点的带权无向图,结点依次以 1, 2, …, N 编号。对任意 1 ≤ u < v ≤ N,都加入一条连接 u 与 v 的边:

给出 n 组询问,每组两个正整数 aᵢ, bᵢ,回答结点 aᵢ 与 bᵢ 之间的最短距离。

样例输入输出
样例 14 4 3
1 2
2 3
4 2
3 5
4
4
3
4
样例 25 2 6
1 2
2 3
4 2
3 5
6 6
2
2
4
2
0
💡
人话翻译:这是一张"超密的图"——任意两个点都直接连着边,边长只有两种:互质走"贵/便宜"的一档,不互质走另一档。
既然任何两点之间都有直飞的边,绕路的意义就只剩下"换一种边长"。
于是最短路径最多两条边:要么直接连,要么飞到某个中转点再飞过去。
中转点只有两个好选择:走 1(1 和谁都互质,两条边都花 p)或走 a × b(它和 a、b 都不互质,两条边都花 q)。
把所有可行方案列出来取最小即可。

🔍 关键词提取

完全图最短路 <= 2 条边分类讨论gcd 判定质因子剥离大数构造中转点

已知条件

项目说明
输入第一行 n、p、q;随后 n 行每行 aᵢ、bᵢ
输出n 行,每行一个整数表示最短距离
结点数N = 10¹⁸ 固定不变
询问数1 ≤ n ≤ 10⁴
询问范围1 ≤ aᵢ, bᵢ ≤ 10⁹
边权1 ≤ p, q ≤ 10⁹
部分分30% 保证 a、b ≤ 50;另有 30% 保证 a、b ≤ 250

需要解决的问题

02
思维导图
整理解题思路的全貌
🔍 最短路 = 在 6 个候选里挑最小可行值
🧠 核心结论
完全图 ⇒ 任意两点直连
所以最短路最多 2 条边
候选只有 0 / p / q / 2p / 2q / p+q
不可能需要 3 条边(见推导)
🛣️ 三种两条边的走法
走 1:a → 1 → b,两条都互质,花 2p
走 a×b:a → a×b → b,两条都不互质,花 2q
混走:一条 p 一条 q,花 p+q
中转点必须落在 1 … N 之内
✅ 可行性判定
0:a == b
p:gcd(a, b) == 1
q:gcd(a, b) > 1
2p / 2q:a > 1 且 b > 1
p+q:有一边的质因子"另一边的数不含"
⚠️ 易错点
忘了 a == b 输出 0
以为 2q 总能走(要 a×b ≤ N)
p+q 判定写成"分解质因数"导致超时
用 int 存 2p / 2q(可达 2 × 10⁹)
漏掉端点为 1 的情形
03
样例手算推导
样例 1、2 的逐条候选推演 + "为什么两条边一定够"的证明

🧮 样例 1(p = 4,q = 3):6 个候选逐条摆开

四条询问:(1,2)、(2,3)、(4,2)、(3,5)。可行记 ✓,不可行记 ✗(不可行的候选直接跳过,不参与取最小)。

询问0(a = b)直接边 p / q2p(走 1)2q(走 a×b)p+q(混走)答案
(1, 2)✗p = 4 ✓(gcd = 1)✗(a = 1)✗(a = 1)7 ✓4
(2, 3)✗p = 4 ✓(gcd = 1)8 ✓6 ✓7 ✓4
(4, 2)✗q = 3 ✓(gcd = 2)8 ✓6 ✓✗(质因子都相同)3
(3, 5)✗p = 4 ✓(gcd = 1)8 ✓6 ✓7 ✓4
1
(1, 2):端点含 1,绕路没用

1 与任何数都互质,所以从 1 出发的每一条边都花 p

走路 1 需要 a > 1,这里 a = 1 不成立

结果只剩直接边 p = 4

答案 4 ✓

2
(2, 3):互质,但 q 更便宜

直接边 gcd = 1 → 4

走 1:2 → 1 → 3,两条都是 p 边 = 8

走 a×b = 6:2 → 6 → 3,两条都是 q 边 = 3 + 3 = 6(6 ≤ N ✓)

混走:2 的质因子 {2}、3 的质因子 {3} 互不相同 → p + q = 7 也可行

min(4, 8, 6, 7) = 4 ✓

3
(4, 2):不互质,q 便宜

直接边 gcd = 2 → 3

走 1 → 8;走 a×b = 8(4 → 8 → 2)→ 6

混走:4 的质因子 {2},2 的质因子 {2},互相都被对方整除 → 不可行

这正是"混走"失败的典型:两边质因子集合完全相同

min(3, 8, 6) = 3 ✓

4
(3, 5):两个不同质数

直接边 gcd = 1 → 4

2p = 8、2q = 6(3 → 15 → 5,两条都是 q 边)

混走 3 → 5 → 5?不行,中转点必须是别的点;取 x = 5 时 gcd(3,5) = 1、gcd(5,5) = 5,但 x = b 不合法

换个 x:x = 10 时 gcd(3,10) = 1、gcd(10,5) = 5 → p + q = 7 可行

min(4, 8, 6, 7) = 4 ✓

🧮 样例 2(p = 2,q = 6):q 贵的时候,绕路就被用上了

这一组把 p、q 的贵贱反了过来:互质边便宜(2),不互质边很贵(6)。

询问直接边2p(走 1)2q(走 a×b)答案说明
(1, 2)p = 2 ✓✗(a = 1)✗(a = 1)2含 1 只能付 p
(2, 3)p = 2 ✓4 ✓12 ✓2直连最省
(4, 2)q = 6 ✓4 ✓12 ✓4不互质 ⇒ 绕道 1,两条 p 边赢
(3, 5)p = 2 ✓4 ✓12 ✓2直连最省
(6, 6)——✗(a = b)✗(a = b)0同一点,距离 0

输出 2 2 4 2 0 ✓

🔑
注意 (4, 2) 这个转折:直连要付 q = 6(因为 4 与 2 不互质),但绕一下 4 → 1 → 2 两条边都互质,只要 2 + 2 = 4。
"直连不是最优"正是本题必须考虑两条边的原因。

🧮 证明:为什么最多 2 条边就够(还有 p+q 为什么是陪跑)

1
先看"端点为 1"的情形

1 与任何正整数都互质,所以从 1 出发(或到达 1)的边一定是 p 边

于是若 a = 1,最短路就是直接边 p(任何路径都至少付 p)

b = 1 同理。a = b = 1 则答案为 0

端点含 1:答案 = p(或 0)

2
再排除"3 条边及以上"

每条边的权值 ≥ min(p, q),所以 k 条边至少 min(p,q) × k

若 p ≤ q:3 条边 ≥ 3p > 2p,而 2p 一定可行(a, b > 1,走 1)

若 q < p:3 条边 ≥ 3q > 2q,而 2q 一定可行(a, b > 1,走 a×b,且 a×b ≤ 10¹⁸ = N)

两种情况都被 ≤ 2 条边的方案严格压住

所以只需考虑 0、1、2 条边

3
最后看 p+q 为什么"永远不是唯一最优"

直接边的权值要么是 p(互质)要么是 q(不互质)

所以 min(p, q) ≤ p + q 恒成立,直接边永远不差于混走

换句话说 p+q 只是个"保险项",加上它不会算错,去掉它也不会漏答案

但为完整起见我们还是把它算上(判可行只要几步 gcd)

候选集合 = { 0, p, q, 2p, 2q, p+q }(可行者取最小)

4
关键数字:a × b ≤ N 恰好成立

题目给 a, b ≤ 10⁹,而 N = 10¹⁸

所以 a × b ≤ 10⁹ × 10⁹ = 10¹⁸ = N,中转点 a×b 永远落在结点范围内

这就是"2q 一定可行"的全部依据,也是本题 N 取 10¹⁸ 而不是别的数的原因

2q 在 a, b > 1 时永远可行

⚠️
三个坑:① a = b 要输出 0,若只写"直接边是 q"会答成 q;② 2p、2q 只在 a, b > 1 时可行,端点等于 1 时必须跳过(此时 x = a 或 x = b,中转点会退化成同一个点);③ 候选值要用 long long:2p 最大 2 × 10⁹,已经超 int。
04
解法对比
六选一分类讨论 vs 小图 Dijkstra(对拍用)

⚔️ 解法对比

🟢 六选一分类讨论(推荐) 推荐

把最短路径的可能形态枚举出来,逐条判可行性,取最小值

  • 每次询问 O(log a)
  • 只有几次 gcd 调用
  • 代码约 40 行
  • n = 10⁴ 瞬间完成
💡
为什么可行:完全图让"路径长度"这个变量被压到 ≤ 2,于是答案只能是 {0, p, q, 2p, 2q, p+q} 中最小的可行者。
而"可行"的判定全是 gcd 级别的运算——把几何问题(最短路)化成了数论判定(互质 / 质因子)。

🟠 小 N 建图跑 Dijkstra

把前若干个结点建成完全图,用 Dijkstra 求最短路

  • 单次 O(N²)
  • N = 10¹⁸ 根本建不出来
  • 只有 N ≤ 2000 时可用
  • 只能当对拍工具
⚠️
它的价值:把小 N 完全图(例如 N = 600)上跑出的真实最短距离和公式比对——
只要 a × b ≤ N,两者就应该完全一致;这是验证这套分类讨论最省事的办法。

📈 性能对比

方案复杂度代码量
六选一分类讨论O(n log a)✅ 正解,约 40 行
小 N 完全图 DijkstraO(N²) 或 O(N² log N)⭕ 只能对拍小数据,约 40 行
SPFA / BFS 在超大图上跑——❌ 图都存不下,无法实现
05
算法流程图
每条询问:先定直接边,再补两条边的候选
开始读入 n、p、q逐条处理询问 (a, b)把 ans 先设成一个很大的数a 与 b 相等吗?是 ✓ans = 0否 ✗继续看直接边直接边:ans = min(ans, gcd(a, b) 为 1 时给 p,否则给 q)a 与 b 都大于 1 吗?是 ✓ans = min(ans, 2p, 2q)否 ✗绕路方案全部不可行混合方案:若 b 有质因子不整除 a(或反过来),ans = min(ans, p+q)输出 ans,回到下一条询问
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔍 最短距离:6 个候选逐条判定

第 1 行输入 n p q,随后 n 行每行 a b。程序会为每条询问列出 6 个候选(0 / p / q / 2p / 2q / p+q)的可行性,并给出最小值。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(六选一分类讨论)

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

typedef long long ll;
const ll BIG = (ll)4e18;

ll gcdll(ll a, ll b) { while (b) { ll t = a % b; a = b; b = t; } return a; }

// 判断 y 是否含有"不整除 x"的质因子:
// 反复把 gcd(u, x) 从 u 里剥掉,剥到最后还剩东西,就说明有"新质因子"
bool hasNewPrime(ll x, ll y) {
    ll u = y;
    while (true) {
        ll d = gcdll(u, x);
        if (d == 1) break;
        u /= d;
    }
    return u > 1;
}

int main() {
    ll n, p, q;
    scanf("%lld %lld %lld", &n, &p, &q);

    while (n--) {
        ll a, b;
        scanf("%lld %lld", &a, &b);
        ll g = gcdll(a, b);
        ll ans = BIG;

        // ① 0 条边:同一个点
        if (a == b) ans = 0;

        // ② 1 条边:直连
        ll direct = (g == 1 ? p : q);
        ans = min(ans, direct);

        // ③ 2 条边:走 1(两条都互质)或走 a*b(两条都不互质)
        if (a > 1 && b > 1) {
            ans = min(ans, 2 * p);
            ans = min(ans, 2 * q);
        }

        // ④ 2 条边:混走(一条互质 + 一条不互质)
        if (hasNewPrime(a, b) || hasNewPrime(b, a)) {
            ans = min(ans, p + q);
        }

        printf("%lld\n", ans);
    }
    return 0;
}
🔑
三个要点:① 候选集合很小,但每一项都要单独判可行性,不能直接把最小值写死;② 2q 能走的关键是a × b ≤ 10¹⁸ = N,中转点 a × b 刚好不越界;③ hasNewPrime 的循环里 u 每轮至少减半,最多 30 轮就结束,不需要写筛法或质因数分解。

📖 关键几行怎么看

代码作用为什么这样写
if (a == b) ans = 0;零条边同一个结点距离为 0,优先于一切正数候选
ll direct = (g == 1 ? p : q);一条边互质付 p,不互质付 q,这就是题目给的边权定义
if (a > 1 && b > 1) { 2p, 2q }两条边的两种纯色走法走 1 要 a、b 都不等于 1;走 a×b 也要 a、b > 1 才不与端点重合
while (true) { d = gcd(u, x); if (d == 1) break; u /= d; }剥离公共质因子循环结束还剩 u > 1 ⇔ 有质因子只属于 y
ans = min(ans, p + q);混走一互质一不互质恰好付 p + q
const ll BIG = 4e18;哨兵比任何可行值都大,写法比 LLONG_MAX 更省心
⚠️
五个坑:① 忘写 a == b,答案会变成 q;② 2p、2q 的可行条件是 a > 1 && b > 1(a = 1 时中转点 1 就是起点,不是两条边);③ p+q 的判定写成"真的分解质因数"——虽然 10⁹ 试除到 31623 也能过,但没必要;④ 候选值用 int 存(2p 可达 2 × 10⁹);⑤ 输出时没注意 n 行(样例 1 是 4 行,样例 2 是 5 行,按输入条数输出)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4 4 3
1 2
2 3
4 2
3 5
4
4
3
4
题面样例 1(混走与走 a×b 都出现)
5 2 6
1 2
2 3
4 2
3 5
6 6
2
2
4
2
0
题面样例 2(q 很贵,绕道 1 更省)
2 100 1
2 3
2 4
2
1
q 便宜:不互质直连 1;互质可绕两条 q 边 = 2
2 1 100
1 4
4 1
1
1
端点含 1:只能付 p,绕路不可行
1 5 5
6 6
0a == b:答案为 0(不是 q = 5)
2 1000000000 1
1000000000 999999999
999999937 999999893
2
2
大数据:两对数都互质但 2q = 2 更省(必须 long long)
✅
自查清单:① a == b 给 0 了吗?② 直接边按 gcd 取 p / q 了吗?③ 2p、2q 加了 a, b > 1 的条件吗?④ p+q 用 gcd 剥离法判定了吗?⑤ 全程 long long 吗?

🚨 易错点清单

⚠️
忘判 a == b:两点重合时距离为 0,任何"走哪条边"的讨论都会把答案写成正数。
⚠️
2p / 2q 的可行条件漏了 a, b > 1:端点等于 1 时中转点会与端点重合,那条"两条边"的路径不成立。
⚠️
把 p+q 判定写成真分解质因数:虽然也能过,但 10⁴ × 31623 的试除很不划算;用 gcd 剥离法只需几十轮。
⚠️
用 int:2p、2q 最大都是 2 × 10⁹,超出 int 范围。
⚠️
输出条数错:样例 1 与样例 2 的询问条数不同(4 与 5),要严格按 n 输出。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n log a)
空间复杂度
O(1)
每次询问
几次 gcd 调用
数据规模
n ≤ 10⁴

时间怎么算的?

空间都用在哪?

只有一个 ans 和几个临时变量,既不建图也不存边——这是本题最漂亮的地方:官方图有 10¹⁸ 个点,我们一个都不建。

✅ n = 10⁴ 的询问量下是"瞬间级"复杂度,真正的难点在分类讨论的完备性,而不在效率。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「完全图 + 边权只与互质有关」通用套路
// 1) 先把"最短路径的形态"压缩到极少条数
//      本题:0 条(同点)/ 1 条(直连)/ 2 条(中转一次)
//      理由:完全图任意两点直连 => 更多条边总能用 ≤ 2 条替代
// 2) 2 条边时,中转点只有两个"颜色极端"的好选择
//      走 1      :和谁都互质     -> 两条 p 边
//      走 a * b  :和 a、b 都不互质 -> 两条 q 边
// 3) 中转点必须落在 [1, N] 内
//      本题 N = 1e18 且 a, b <= 1e9  =>  a * b <= 1e18 恰好成立
//      这是 2q 永远可行的唯一依据
// 4) "存在质因子只属于某一边"不要真分解
//      while (true) { d = gcd(u, x); if (d == 1) break; u /= d; }
//      u > 1  =>  y 有质因子不整除 x

// 复杂度 O(n log a),不建图、不存边、不跑最短路

// 容易忽略的三种退化
//   a == b        -> 答案 0
//   a == 1 或 b == 1 -> 只能付 p(1 与一切数互质)
//   q < p 时      -> 绕两条 q 边常常比直连更便宜

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
最短路径形态压缩把"路径长度"从任意压到 ≤ 2完全图 / 稠密图上的最短路、直径、离心率问题
构造中转点用 1 和 a×b 造出"全互质""全不互质"两条路数论构造类题目:凑出满足条件的数
有界中转点中转点必须 ≤ N,所以要先验证 a×b ≤ N所有"构造中间量"的题都要检查值域
gcd 剥离法反复除以 gcd,判断是否有"新质因子"判定"两个数的质因子集合包含关系"、LCM / GCD 组合问题
小候选集合枚举答案只在几个值里挑,逐个判可行一切"答案形态有限"的分类讨论题
🌟
思考题:如果把边长规则改成"gcd(u, v) = 1 付 p,gcd(u, v) > 1 且两者都是偶数付 q,其余付 r",这套"最多两条边"的结论还成立吗?(提示:成立,但候选集合要重新枚举——因为"三档边权"下两条边的组合会变成p+p, q+q, r+r, p+q, p+r, q+r 六种,而每一种的可行性都要像本题一样构造出合适的中转点来验证或反驳。这类题的核心能力始终是:先证明路径形态有限,再为每种形态找构造;找不到构造就说明它不可行。)