题解：P11275 微观戏剧

cff_0102 · 2024-11-15 08:48:16 · 题解

当 x=y 时，直接输出 0 即可。

由于两个数之间的连边长度为它们的最小公倍数，而 a 和 b 的最小公倍数必然大于等于 a 和 b，所以要从 x 走到 y，中间经过的最大的边必然大于等于 x 和 y。

当 x 和 y 存在倍数关系，那么它们之间就连了一条长为 \max{(x,y)} 的边，根据之前的推理，直接走这条边显然是最优的，因为不可能存在长度小于它的路径了。

如果 x 和 y 不存在倍数关系，那么有两种可行的做法：

1. 直接从 x 走到 y。
2. 从 x 出发，经过若干个“中转点”，再走到 y。

前者的路径长度为 \operatorname{lcm}(x,y)。至于后者，考虑走的第一条和最后一条边，它们的长度必然分别大于等于 x 和 y，所以最终路径的长度不可能小于 x+y。而从 x 走到 1，再从 1 走到 y 的做法的最终路径长度恰好即为 x+y，因此这样做的最短路径长度为 x+y。

当 x,y 不存在倍数关系时，\operatorname{lcm}(x,y)\ge2\times\max(x,y)>x+y，因此 x+y 是更优的答案。此时输出 x+y 即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t;cin>>t;while(t--){
        int x,y;cin>>x>>y;
        int a=__gcd(x,y);
        if(x==y)cout<<0<<endl;
        else if(a==x)cout<<y<<endl;
        else if(a==y)cout<<x<<endl;
        else cout<<x+y<<endl;
    }
    return 0;
}