[P14079]最短距离-题解

72728abcd · 2025-09-27 17:44:32 · 题解

Update on 2025/12/13 :
修复了 LaTeX 问题。
本题需要分类讨论，共 3 种情况：
1.a,b 互质。此时我们明显能想到输出 p，但要是 q 比 p 小很多，还真不一定。我们推一下，容易想到以 a×b 作为桥梁，这样，代价就是 2q。输出 p 与 2q 之间小的那个即可。千万要注意，当 a,b 之间有一个是 1 的时候，一定要输出 p！
2.a,b 不互质。同理，输出 q 与 2p 之间小的那个即可。
3.一定不要忘了 a=b 的时候输出 0！

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,p,q;
    cin>>n>>p>>q;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        if(a==b)
        {
            cout<<0<<endl;
            continue;
        }
        if(__gcd(a,b)==1)
        {
            if(a==1||b==1)
            {
                cout<<p<<endl;
            }
            else
            {
                cout<<min(p,2*q)<<endl;
            }
        }
        else
        {
            cout<<min(q,2*p)<<endl;
        }
    }
    return 0;
}