题解：P14079 [GESP202509 八级] 最短距离

· · 题解

这题一看就是要 O ( \log{a} ) 以内出结果的题 ！！！ （别问我怎么知道的）。

本题就是说对于两个数 a 和 b, 若 gcd(a, b) = 1 , 则连一条边权为 p 的边， 否则连一条边权为 q 的边。 问 a 和 b 的最短路。

我们分两种情况讨论：

  1. 当 gcd(a, b) = 1 时， ans 可以等于 p ，也可以等于 2 \times q, 因为可以先从点 a 到点 a \times b， 再从点 a \times b 到点 b 。

  2. 当 gcd(a, b) > 1 时， ans 可以等于 q ，也可以等于 2 \times p, 因为可以先从点 a 到点 1， 再从点 1 到点 b 。

但是还要特判一下 ！！！

当 a = b 时， ans = 0 。

当 a = 1 或 b = 1 时， ans = p 。

以上就是正解思路了。

时间复杂度 O ( n \log{a} ) , 可以通过本题。

空间复杂度 O ( 1 ) , 包可以通过本题的。

最后， 你们最爱的代码来了 ！！！

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int n;
LL ans, p, q, a, b, g;
int main() {
    scanf("%d%lld%lld", &n, &p, &q);
    while(n --) {
        ans = 1e18;
        scanf("%lld%lld", &a, &b);
        if(a == b) {
            puts("0");
            continue;
        }
        if(a == 1 || b == 1) {
            printf("%lld\n", p);
            continue;
        }
        g = __gcd(a, b);
        if(g == 1) ans = min(p, q * 2);
        else ans = min(q, p * 2);
        printf("%lld\n", ans);
    }
    return 0;
}

代码很简单， 按上面的思路做就行。