G8015 [GESP202509 八级] 最短距离 题解

知识点：最大公约数、分类讨论、路径性质。

解题思路

相同节点距离0。gcd(a,b)>1时取min(q,2p)；有一端为1时距离p；其余互质且都大于1时取min(p,2q)。

为什么正确

非互质可直接走q或经1走两条p边；互质且非1可直接走p或经ab走两条q边。任意更优路线若含直接类边已有下界，否则至少两条另一类边。

易错点

题目a,b≤10^9，因此ab≤10^18是合法中间点；不能对任意更大范围未经证明复用结论。

复杂度

每组时间O(log min(a,b))，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long p,q;
    cin>>n>>p>>q;
    while(n--) {
        long long a,b;
        cin>>a>>b;
        long long ans;
        if(a==b)ans=0;
        else if(gcd(a,b)>1)ans=min(q,2*p);
        else if(a==1||b==1)ans=p;
        else ans=min(p,2*q);
        cout<<ans<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。