5386 - 最短距离
题目描述
给定正整数 p, q 以及常数 N = 10^{18} 。现在构建一张包含 N 个结点的带权无向图，结点依次以 1, 2, \dots, N 编号。
对于任意满足 1 \le u \lt v \le N 的 u, v ，向图中加入一条连接结点 u 与结点 v 的无向边，边权取决于 u 和 v 是否互质：
- 若 u 与 v 互质（即 u, v 的最大公因数为 1 ），则连接结点 u 与结点 v 的无向边长度为 p ；
- 否则，连接结点 u 与结点 v 的无向边长度为 q 。
现在给定 n 组询问，第 i （ 1 \le i \le n ）组询问给定两个正整数 a_i, b_i ，你需要回答结点 a_i 与结点 b_i 之间的最短距离。
输入
第一行：三个正整数 n, p, q ，分别表示查询数量、结点编号互质时的边权，以及结点编号不互质时的边权。
接下来 n 行，每行两个正整数 a_i, b_i ，表示一组询问。
输出
输出共 n 行，每行一个整数，表示结点 a_i 与结点 b_i 之间的最短距离。
样例
输入
4 4 3 1 2 2 3 4 2 3 5
输出
4 4 3 4
输入
5 2 6 1 2 2 3 4 2 3 5 6 6
输出
2 2 4 2 0
说明
数据范围
对于30\% 的测试点，保证 1 \le n \le 10 , 1 \le a_i,b_i \le 50 。
对于另外 30\% 的测试点，保证 1 \le a_i,b_i \le 250。
对于所有测试点，保证 1 \le n \le 10^4 , 1 \le a_i,b_i \le 10^9, 1 \le p,q \le 10^9 。
来源
GESP 2025年09月认证 C++8级真题
标签
