题解：P14079 [GESP202509 八级] 最短距离
zhujianheng
·
·
题解
首先考虑 a=b 时，显然答案为 0。
再考虑 a=1 时，答案显然为 p。
然后分类讨论。
$\gcd(a,b) = 1$ 且 $a,b \ge 2$ 时，答案可能为 $p$。但也存在整数 $k$，使得 $\gcd(a,k),\gcd(b,k) \ge 2$，就比如 $k=ab$ 时，答案为 $\min(p,2q)$。
$\gcd(a,b) \ge 2,a,b \ge 2$ 时，答案可能为 $q$，但也存在整数 $k$，使得 $\gcd(a,k)=\gcd(b,k)=1$，当 $k=ab+1$ 时，$\gcd(a,k)=\gcd(b,k)=1$，证明很显然，答案为 $\min(q,2p)$。
这时有人想到，$ab+1$ 会不会超出 $10^{18}$？不会的。因为只有 $a=b=10^9$ 时才会取到 $ab+1>10^{18}$，而这种情况已经在 $a=b$ 情况中考虑了。
所以时间复杂度 $O(T \log V)$，$V$ 是 $a,b$ 的值域，本题中为 $10^9$。
AC Code:
```
#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;
}
```