简答题
偏难
#19970
最短距离
最短距离



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 100005;
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) {
// 互质,可以合并处理花费p
ans = min(ans, p);
} else {
// 不互质,合并处理花费q
ans = min(ans, q);
}
}
printf("%d\n", ans);
}
return 0;
}</pre>
这道题暂未补解析。