P9484 「LAOI-1」GCD 题解
Coffins
·
·
题解
前言
赛时 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)$ 大的话 $z$ 中一定有 $y$ 不需要的因子，最终还要除去，而 $x$ 已经加倍过，出去后走的就要比原来远，故也不如直接走到 $\gcd(x,y)$ 优。
综上，答案为 $x+y-2\gcd(x,y)$。
## Code
```cpp
#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;
}
```