A71932 | 最短距离

给定正整数 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 之间的最短距离。