N = 10¹⁸ 的完全图,任意两点之间最多只需要走两条边:在 0 / p / q / 2p / 2q / p+q 里挑可行者取最小值。
给定正整数 p、q 以及常数 N = 10¹⁸。构建一张包含 N 个结点的带权无向图,结点依次以 1, 2, …, N 编号。对任意 1 ≤ u < v ≤ N,都加入一条连接 u 与 v 的边:
u, v 互质(最大公因数为 1),边长为 p;q。给出 n 组询问,每组两个正整数 aᵢ, bᵢ,回答结点 aᵢ 与 bᵢ 之间的最短距离。
| 样例 | 输入 | 输出 |
|---|---|---|
| 样例 1 | 4 4 3 | 4 |
| 样例 2 | 5 2 6 | 2 |
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 |
p + p(中转点与两端都互质)、q + q(中转点与两端都不互质)、p + q(一互质一不互质)2p:取中转点 1,只要 a, b > 1 就行;2q:取中转点 a × b,需要 a, b > 1 且 a × b ≤ N(本题 10⁹ × 10⁹ = 10¹⁸ = N,刚好放得下!);p + q:需要存在一个质因子"只属于其中一边"p + q 可行?即"b 有某个质因子不整除 a"(或反过来)。不必真的分解质因数,用 while (gcd(u, x) > 1) u /= gcd(u, x) 把"公共质因子"剥掉,最后 u > 1 就说明还有新质因子a = b:距离为 0,这是唯一"零条边"的答案四条询问:(1,2)、(2,3)、(4,2)、(3,5)。可行记 ✓,不可行记 ✗(不可行的候选直接跳过,不参与取最小)。
| 询问 | 0(a = b) | 直接边 p / q | 2p(走 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 出发的每一条边都花 p
走路 1 需要 a > 1,这里 a = 1 不成立
结果只剩直接边 p = 4
答案 4 ✓
直接边 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 ✓
直接边 gcd = 2 → 3
走 1 → 8;走 a×b = 8(4 → 8 → 2)→ 6
混走:4 的质因子 {2},2 的质因子 {2},互相都被对方整除 → 不可行
这正是"混走"失败的典型:两边质因子集合完全相同
min(3, 8, 6) = 3 ✓
直接边 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 ✓
这一组把 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 ✓
q = 6(因为 4 与 2 不互质),但绕一下 4 → 1 → 2 两条边都互质,只要 2 + 2 = 4。1 与任何正整数都互质,所以从 1 出发(或到达 1)的边一定是 p 边
于是若 a = 1,最短路就是直接边 p(任何路径都至少付 p)
b = 1 同理。a = b = 1 则答案为 0
端点含 1:答案 = p(或 0)
每条边的权值 ≥ 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 条边
直接边的权值要么是 p(互质)要么是 q(不互质)
所以 min(p, q) ≤ p + q 恒成立,直接边永远不差于混走
换句话说 p+q 只是个"保险项",加上它不会算错,去掉它也不会漏答案
但为完整起见我们还是把它算上(判可行只要几步 gcd)
候选集合 = { 0, p, q, 2p, 2q, p+q }(可行者取最小)
题目给 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。把最短路径的可能形态枚举出来,逐条判可行性,取最小值
{0, p, q, 2p, 2q, p+q} 中最小的可行者。把前若干个结点建成完全图,用 Dijkstra 求最短路
a × b ≤ N,两者就应该完全一致;这是验证这套分类讨论最省事的办法。| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 六选一分类讨论 | O(n log a) | ✅ 正解,约 40 行 |
| 小 N 完全图 Dijkstra | O(N²) 或 O(N² log N) | ⭕ 只能对拍小数据,约 40 行 |
| SPFA / BFS 在超大图上跑 | —— | ❌ 图都存不下,无法实现 |
第 1 行输入 n p q,随后 n 行每行 a b。程序会为每条询问列出 6 个候选(0 / p / q / 2p / 2q / p+q)的可行性,并给出最小值。
点按钮开始 →
#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 行,按输入条数输出)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 4 3 | 4 4 3 4 | 题面样例 1(混走与走 a×b 都出现) |
5 2 6 | 2 2 4 2 0 | 题面样例 2(q 很贵,绕道 1 更省) |
2 100 1 | 2 1 | q 便宜:不互质直连 1;互质可绕两条 q 边 = 2 |
2 1 100 | 1 1 | 端点含 1:只能付 p,绕路不可行 |
1 5 5 | 0 | a == b:答案为 0(不是 q = 5) |
2 1000000000 1 | 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 剥离法只需几十轮。2p、2q 最大都是 2 × 10⁹,超出 int 范围。n 输出。gcd:一次求 gcd(a, b),最多两次"剥离质因子"循环u 每轮至少除以 2(因为 gcd > 1),所以最多约 log₂(10⁹) ≈ 30 轮O(n log a),n = 10⁴ 时大约几十万次运算只有一个 ans 和几个临时变量,既不建图也不存边——这是本题最漂亮的地方:官方图有 10¹⁸ 个点,我们一个都不建。
✅ n = 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 六种,而每一种的可行性都要像本题一样构造出合适的中转点来验证或反驳。这类题的核心能力始终是:先证明路径形态有限,再为每种形态找构造;找不到构造就说明它不可行。)