自动搬运

查看原文

来自洛谷，原作者为

	Coffins 棺中之人

搬运于2025-08-24 22:48:47，当前版本为作者最后更新于2023-07-29 22:22:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

赛时 5min 切了，然后就没继续比赛了。

这题目其实就是纯白给签到题然而我第一次提交被卡了输入

解法

考虑条件 $\gcd(i,j)=i,\operatorname{lcm} (i,j)=j$ ，显然等价于 $i|j$，也就是说当一个数为一个数的倍数时，两个数之间有边。

然后考虑如何最小化路径。

感性上理解是把 $x$，$y$ 都跳到 $\gcd(x,y)$ 处，那么如何证明？

（不妨设 $y\le x$）

考虑把 $x$ 往 $y$ 走，那么 $x$ 一定要先到达一个 $y$ 的因数/倍数 $z$。

情况一：倍数

把 $x$ 加倍后至少走了 $x\ge \gcd(x,y)$ 步，所以一定不比往 $\gcd(x,y)$ 走优。

情况二：因数

$z$ 比 $\gcd(x,y)$ 小的话显然不比向 $\gcd(x,y)$ 走优； $z$ 比 $\gcd(x,y)$ 大的话 $z$ 中一定有 $y$ 不需要的因子，最终还要除去，而 $x$ 已经加倍过，出去后走的就要比原来远，故也不如直接走到 $\gcd(x,y)$ 优。

综上，答案为 $x+y-2\gcd(x,y)$。

Code

#include<bits/stdc++.h>
int t,n,q;
int x,y;
int gcd(int a,int b)
{
	while(b^=a^=b^=a%=b);
	return a;
}
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>n>>q;
		for(int i=1;i<=q;i++)
		{
			cin>>x>>y;
			cout<<x+y-2*gcd(x,y)<<'\n';
		}
	 } 
	return 0;
}