专栏文章

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

zzhujianheng
P14079题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minqwqlb
此快照首次捕获于
2025/12/02 06:53
3 个月前
此快照最后确认于
2025/12/02 06:53
3 个月前
查看原文
首先考虑 a=ba=b 时，显然答案为 00。
再考虑 a=1a=1 时，答案显然为 pp。
b=1b=1 同理。
然后分类讨论。
gcd⁡(a,b)=1\gcd(a,b) = 1 且 a,b≥2a,b \ge 2 时，答案可能为 pp。但也存在整数 kk，使得 gcd⁡(a,k),gcd⁡(b,k)≥2\gcd(a,k),\gcd(b,k) \ge 2，就比如 k=abk=ab 时，答案为 min⁡(p,2q)\min(p,2q)。
gcd⁡(a,b)≥2,a,b≥2\gcd(a,b) \ge 2,a,b \ge 2 时，答案可能为 qq，但也存在整数 kk，使得 gcd⁡(a,k)=gcd⁡(b,k)=1\gcd(a,k)=\gcd(b,k)=1，当 k=ab+1k=ab+1 时，gcd⁡(a,k)=gcd⁡(b,k)=1\gcd(a,k)=\gcd(b,k)=1，证明很显然，答案为 min⁡(q,2p)\min(q,2p)。
这时有人想到，ab+1ab+1 会不会超出 101810^{18}？不会的。因为只有 a=b=109a=b=10^9 时才会取到 ab+1>1018ab+1>10^{18}，而这种情况已经在 a=ba=b 情况中考虑了。
所以时间复杂度 O(Tlog⁡V)O(T \log V)，VV 是 a,ba,b 的值域，本题中为 10910^9。
AC Code:
CPP
#include<bits/stdc++.h>
using namespace std;
int main(){
    int T,p,q;
    cin>>T>>p>>q;
    while(T--){
        int a,b;
        cin>>a>>b;
        if(a==b) cout<<0<<endl;
        else if(a==1||b==1) cout<<p<<endl;
        else if(__gcd(a,b)==1) cout<<min(p,2*q)<<endl;
        else cout<<min(q,2*p)<<endl;
    }
    return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...