自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 23:05:59，当前版本为作者最后更新于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;
}