题目描述
给定正整数 p,q 以及常数 N=1018。现在构建一张包含 N 个结点的带权无向图，结点依次以 1,2,…,N 编号。对于任意满足 1≤u<v≤N 的 u,v，向图中加入一条连接结点 u 与结点 v 的无向边，边权取决于 u,v 是否互质：
- 若 u,v 互质（即 u,v 的最大公因数为 1），则连接结点 u 与结点 v 的无向边长度为 p；
- 否则连接结点 u 与结点 v 的无向边长度为 q。
现在给定 n 组询问，第 i（1≤i≤n）组询问给定两个正整数 ai,bi，你需要回答结点 ai 与结点 bi 之间的最短距离。
输入格式
第一行，三个正整数 n,p,q，分别表示询问数量，结点编号互质时的边权，以及结点编号不互质时的边权。
接下来 n 行，每行两个正整数 ai,bi，表示一组询问。
输出格式
输出共 n 行，每行一个整数，表示结点 ai 与结点 bi 之间的最短距离。
输入输出样例
输入 #1
4 4 3 1 2 2 3 4 2 3 5
输出 #1
4 4 3 4
输入 #2
5 2 6 1 2 2 3 4 2 3 5 6 6
输出 #2
2 2 4 2 0
说明/提示
对于 30% 的测试点，保证 1≤n≤10，1≤ai,bi≤50。
对于另外 30% 的测试点，保证 1≤ai,bi≤250。
对于所有测试点，保证 1≤n≤104，1≤ai,bi≤109，1≤p,q≤109。
题目大意：给定一个正整数x，需要变为y，每次可以将x变为1e18以内的任何数字z，但是代价按照以下方式计算:gcd(x,y)==1时代价为p，否则为q,给定n,p,q，之后n行，每行一组x,z。输出最小的变换次数
考点：最大公因数
思路解析：
①若x==y则答案为0
②如果gcd(x,y)==1，可以直接变换,代价为p，也可以选择x≠1且y≠1时将x变为lcm(x,y)*m再变为y，代价为2*q，但是需要满足1<=m,且lcm(x,y)*m<=1e18
③若gcd(x,y)!=1
则可以将x变为m再变为y，代价为2*p，但是需要满足gcd(x,m)==1且gcd(y,m)==1
参考程序
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int n, p, q;
int a, b;
int ans;
int gcd(int a, int b) {
if (!a || !b) return a + b;
return gcd(b, a % b);
}
int main() {
scanf("%d%d%d", &n, &p, &q);
while (n--) {
scanf("%d%d", &a, &b);
if (a == b)
ans = 0;
else if (a == 1 || b == 1)
ans = p;
else {
ans = min(p + p, q + q);
if (gcd(a, b) == 1)
ans = min(ans, p);
else ans = min(ans, q);
}
printf("%d\n", ans);
}
return 0;
}