P11275 微观戏剧
Description
对于一个无限个点的无向图，其中 i 连向 j 的边的边权为 \operatorname{lcm}(i,j)。
每一次询问 u 走到 v 的最小边权和。
## Solution
需要特判：如果 $u=v$，那么答案为 `0`。
设 $i$ 走向 $j$ 的边权为 $w(i,j)$。
首先，显然有一种走法，就是直接从 $u$ 走向 $v$，边权和是 $\operatorname{lcm}(u,v)$。
不然，分类讨论其他的走法。
1. 只经过一个点 $x$。
当前答案：
$$
Ans=w(u,x)+w(x,y)\\
\ge u+v\\
=w(u,1)+w(1,v)
$$
2. 经过不止一个点，设从 $u$ 走出去的第一个点为 $p_1$，走回 $v$ 的最后一个点为 $p_m$。
$m$ 是除了 $u$ 和 $v$ 的其他点的数量。
当前答案：
$$
Ans=w(u,p_1)+w(p_1,p_2)+\cdots+w(p_{m-1},p_{m})+w(p_m,v)\\
\ge w(u,p_1)+w(p_m+v)\\
\ge u+v\\
\ge w(u,1)+w(1,v)
$$
显然，能够发现所有走法都不优于从 $u$ 走到 `1` 再走回 $v$。
所以答案就是 $\min(\operatorname{lcm}(u,v),u+v)$。
## Code
```cpp
#include<bits/stdc++.h>
#define int long long
#define ll __int128_t
using namespace std;
inline int Gcd(int x,int y){
while(y)swap(x=x%y,y);
return x;
}
inline void solve(){
int n,m;cin>>n>>m;
if(n==m){
cout<<"0\n";
return ;
}
ll ans=n+m;
ll ano=(ll)n*m/Gcd(n,m);
int res;
if(ans<ano)res=ans;
else res=ano;
cout<<res<<"\n";
}
signed main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int T;cin>>T;while(T--)solve();
}
```